Téléportation – Épreuve régionale 2004

Énoncé¶

On vous décrit un parcours, sous la forme d'un tableau d'entiers, à une dimension. Vous partez de la première case du parcours (d'indice $0$), et devez atteindre la dernière, en un minimum d'étapes possibles.

À chaque étape, vous vous trouvez à une position du parcours, et vous avez trois possibilités de déplacement :

• Aller sur la case de droite (indice suivant dans le tableau).
• Aller sur la case de gauche, (indice précédent dans le tableau).
• Vous téléporter à la case dont l'indice est indiqué dans la case sur laquelle vous vous trouvez actuellement.

À aucun moment, vous ne pouvez sortir du tableau, et vous n'avez pas le droit d'aller sur une case contenant la valeur $-1$.

Entrée¶

Vous devez lire deux lignes sur l'entrée :

• La première ligne contient un entier, $N$, le nombre de cases du tableau.
• La deuxième ligne contient $N$ entiers, séparés par des espaces : les valeurs contenues dans les cases du parcours, de $-1$ à $N-1$.

Sortie¶

Vous devez écrire un entier sur la sortie : le nombre minimum de déplacements nécessaires pour arriver sur la dernière case du parcours (d'indice $N - 1$), ou $-1$, s'il n'est pas possible de sortir.

Contraintes¶

• $1 \le N \le 1\,000$