Zadanie

Elektromagnetické čo???

Počet bodov: 35

Melón Lusk, novodobý génius a technokráľ, sa po náročnom 28-hodinovom dni práce rozhodol vyrelaxovať príjemným večerom pri televízií. Zobral ovládač, zapol Faux news a čo to len nepočuje? V Kalifornii sa rozhodli opäť oživiť výstavbu vysokorýchlostných železníc z LA do San Francisca.

A vtom to prišlo. Taký dobrý nápad, aký už roky nemal. Ehhh… Elektromagnetické katapulty! Áno, síce ešte neexistujú, ale keď (ak) raz budú, isto budú lepšie ako nejaké zastaralé vlaky!

No ale ak majú byť katapulty lepšie než železnice, musia danú trasu pokryť efektívnejšie. Dokážte Melónovi, že to tak naozaj je (a neopovážte sa prísť k opačnému záveru!).

Úloha

Na priamke na pozíciach \(1\) až \(n\) leží \(n\) katapultov, pričom katapult na pozícií \(i\) má silu \(a_i\). Keď stojíme na nejakej pozící \(i\), vieme použiť katapult na nej a vystreliť sa o nanajvýš \(a_i\) pozícií doprava.

Zistite, koľko najmenej katapultov je potrebné použiť, aby sme sa dostali z pozície \(1\) – Los Angeles do pozície \(n\) – San Francisca.

Vstup a Výstup

Prvý riadok obsahuje číslo \(n\) (\(2 \leq n \leq 5 \cdot 10^5\)) – počet katapultov. Na následujúcom riadku sa nachádza \(n\) medzerou oddelených celých čísel \(a_i\) (\(0 \leq a_i \leq 5 \cdot 10^5\)) – sily jednotlivých katapultov. Na výstup vypíšte jeden riadok s jediným číslom – minimálnym počtom katapultov, ktoré musíme použiť aby sme sa dostali k poslednému.

Ak taká cesta neexistuje, vypíšte -1.

Príklad

Input:

4
2 2 0 4

Output:

2

Z pozície \(1\) sa posunieme o jednu pozíciu na \(2\) a odtiaľ vieme ísť priamo do cieľa.

Input:

6
0 4 2 1 4 3

Output:

-1

Z prvej pozície sa nemáme ako dostať.