canguri

În stepa nesfârşită, $n$ canguri s-au aliniat unul lângă celălalt la linia de start, pentru a participa la o cursă în linie dreaptă. La semnalul de începere a cursei fiecare cangur va sări, în ritm constant şi în salturi de aceeaşi lungime, până când toţi cangurii, la ultimul salt, vor ateriza simultan pe linia de finish. Care este lungimea minimă a traseului ştiind că toţi cangurii pleacă în alcelaşi moment în cursă şi fiecare face cel puţin $3$ salturi pe traseul dat.

Cerinţă

Ştiind numărul cangurilor şi lungimea saltului fiecărui cangur, să se determine lungimea minimă a traseului pe care se poate desfăşura cursa.

Date de intrare

Fişierul de intrare canguri.in conţine pe prima linie $n$, numărul de canguri iar pe următoarea linie, $n$ numere naturale nenule separate prin câte un spaţiu $a_1, a_2, \dots, a_n$, reprezentând lungimea în metri a saltului fiecărui cangur.

Date de ieşire

Fişierul de ieşire canguri.out va conţine pe prima linie un număr întreg, reprezentând lungimea minimă a traseului cursei, măsurată în metri.

Restricţii şi precizări

• Lungimea labei picioarelor cangurilor este neglijabilă în raport cu lungimea saltului.
• Lungimea traseului nu depăşeşte $2\ 100\ 000\ 000$ metri.
• $1 \leq n \leq 500$
• $1 \leq a_i \leq 100$

Exemplu

canguri.in

4
12 6 24 8

canguri.out

3

Explicație

Primul cangur face $6$ salturi, al doilea $12$ salturi, al treilea $3$ salturi iar al patrulea $9$ salturi.