3. Ach Chlapče, nemosúr sa!

Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a skús sa pozrieť ako by mal vyzerať ideálny program. Ak zaťiaľ programovať nevieš, ale chcel/a by si vedieť možeš skúsiť náš python tutoriál.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Merlinovi na [email protected] alebo Miškovi na [email protected]

Počas dlhých zimných večerov sa Merlin s Miškom chceli zahrať ich obľúbenú spoločenskú hru, Chlapče, nemosúr sa!. Nastal ale menší problém, Merlin spapal kocku. Po dlhom rozmýšľaní sa rozhodli, že si hru zahrajú s trochu pozmenenými pravidlami.

Úloha

Merlin s Miškom na každé z \(n\) políčok napísali číslo \(a_i\), najväčší počet políčok, o ktorý sa figúrka z tohto políčka môže pohnúť. Nezabúdajte, že figúrka sa môže pohnúť aj o menej ako \(a_i\) políčok. Na koľko najmenej ťahov sa teraz dokáže dostať figúrka zo začiatočného na koncové políčko?

Formát vstupu

Na prvom riadku vstupu dostanete číslo \(n\) (\(2 \leq n \leq 10^6\)), počet políčok na hracom plániku. V druhom riadku nasleduje \(n\) čísel. Číslo \(a_i\) (\(1 \leq a_i \leq 10^6\)) je číslo napísané na \(i\)-tom políčku.

Formát výstupu

Vypíšte jedno číslo, najmenší počet ťahov potrebný na dostanie figúrky z políčka číslo \(1\) na políčko číslo \(n\).

Hodnotenie

Existuje 5 sád vstupov. Pre prvú sadu navyše platí, že \(n \leq 100\). Pre druhú sadu platí, že \(n \leq 10^4\). Pre tretiu sadu platí, že \(max(a_i) \leq 10\). Posledné dve sady nemajú žiadne ďalšie obmedzenia.

Príklad

Input:

4
1 3 2 1

Output:

2

Input:

7
2 2 1 2 1 1 5

Output:

4

Figúrku môžeme postupne posúvať o 1, 2, 2 a 1 políčko, čím sa dostaneme na koniec.