Fișierul intrare/ieșire	pgb.in, pgb.out	Sursă	Concurs admitere IQ Academy
Autor	clasică	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.12 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	0.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Problema grea cu Bixi

Broscuța Bixi se află pe prima poziție a unui vector V cu N elemente numere naturale. Dintr-o poziție i, aceasta poate sări:

• Pe orice poziție din intervalul ].

Cerință

Să se afișeze numărul maxim de sărituri prin care Bixi poate ajunge pe ultima poziție din vector. Dacă acest lucru nu este posibil, se va afișa -1.

Date de intrare

Fișierul de intrare pgb.in conține pe prima linie numărul N, iar pe următoarea linie N elemente numere naturale, reprezentând valorile lui V.

Date de ieșire

Fișierul de ieșire pgb.out conține o singură valoare, reprezentând răspunsul cerinței.

Restricții

• 1 ≤ N ≤ 100.000
• 0 ≤ V[i] ≤ 100.000
• Bixi nu are voie să sară în afara vectorului.
• Suma valorilor din V nu va depăși 1.000.000.

Exemplu