Alexandru, mare informatician, a decis să își impresioneze prietenii cu următoarea problemă: Dându-se un vector cu N numere naturale nenule, se întreabă care este numărul minim de mulțimi cu numere consecutive de forma {1...K} în care acesta poate fi împărțit. Spre exemplu vectorul A = {1, 3, 2, 2, 1, 4} poate fi împărțit în număr minim de partiții astfel {1, 2, 3, 4}, {1, 2}.

Cerința

Cum această problemă a fost prea dificilă pentru prietenii săi, Alexandru te roagă pe tine să o rezolvi.

Date de intrare

Fișierul de intrare mmult.in conține pe prima linie numărul N, iar pe a doua linie N numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire mmult.out va conține pe prima linie numărul S, reprezentând răspunsul problemei date de Alex.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000
• dacă problema nu are soluție, se va afișa -1

Exemplu:

mmult.in

6
1 3 2 2 1 4

mmult.out

2