U Srebrogradu se dogodila poplava i svi električni kabeli su se pokidali. Zato je gradonačelnik Srebrograda pozvao električara Leona da mu pomogne vratiti struju svim kućama. U Srebrogradu se nalazi \(n\) kuća označenih redom brojevima od 1 do \(n\) te svaka kuća ima svoju cijenu spajanja \(x_i\). Gradonačelnik srebrograda voli višekratnike i od Leona je zatražio da spaja kuće na sljedeći način. Kuću \(i\) i kuću \(j\) može spojiti električnim kabelom ako je \(j\) višekratnik od \(i\) i to spajanje košta \(x_i\) srebrnjaka. Oprez, bitan je redoslijed.

Na taj način će kuća \(j\) imati struju ako je neposredno kabelima spojena s kućom 1.

Leon zna da samo prva kuća ima struju i želi potrošiti što manje srebrnjaka tako da sve kuće imaju struju. Molimo vas pomozite Leonu i izračunajte koliko mu je najmanje srebrnjaka potrebno da spoji sve kuće električnim kabelima.

Ulaz

U prvom retku dan je jedan broj \(n\) \((1 \leq n \leq 10^5)\), broj kuća u Srebrogradu.
U sljedećem retku dano je \(n\) brojeva \(x_i\), \((1 \leq x_i \leq 10^9)\), cijene spajanja kuća.

Izlaz

U jedini redak ispišite jedan broj, najmanju količinu srebrnjaka potrebnu da sve kuće dobiju struju.

U 50% testnih slučajeva će vrijediti \(1 \leq n \leq 2000\).

Primjer ulaza

5
4 2 1 3 12

Primjer izlaza

14

Pojašnjenje

Leon će spojiti kuće \((1,2)\), \((1,3)\), \((1,5)\) i \((2,4)\).

Primjer ulaza

3
1 2 1

Primjer izlaza

2