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

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

Vezi soluțiile trimise | Statistici

Problema medie 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 poziția i – 1
• Pe poziția i + 1
• Pe orice poziție j pentru care V[i] == V[j]

Cerință

Să se afișeze numărul minim de sărituri prin care Bixi poate ajunge pe ultima poziție din vector.

Date de intrare

Fișierul de intrare pmb.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 pmb.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.
• Pentru 40% dintre teste, 1 ≤ N ≤ 1.000

Exemplu