Duota sveikųjų skaičių A seka, kurios ilgis n. Turite rasti sekos A posekį A', kuriame kiekvienas elementas a'_{i} dalijasi iš ankstesnio elemento a'_{i-1}.
Sekos posekis sudaromas išbraukiant kai kuriuos elementus, nepakeičiant likusių elementų pozicijų.
Koks yra mažiausias elementų skaičius, kurį reikia ištrinti?
Input
Pirmoje įvesties eilutėje nurodytas sekos ilgis n (1 \le n \le 8000).
Antroje eilutėje n sveikų skaičių (-10^9 \le a_i \le 10^9).
Output
Išveskite minimalų elementų skaičių, kurį turime išbraukti.
Examples
| standard input | standard output |
|---|
| 6
3 2 6 18 12 36
| 2
|
| 4
1 -4 16 -64
| 0
|
Note
Pirmajame pavyzdyje pašalinus du elementus galime gauti seką (3,6,18,36) arba (2,6,12,36).
Atminkite, kad nulis dalijasi iš bet kurio skaičiaus, bet joks skaičius nedalomas iš nulio.