Challenge 5 - Descente en rappel

Après avoir parcouru un long couloir du temple que vous êtes en train d'explorer, vous manquez tout juste de tomber dans le vide ! Votre couloir mène à un gouffre très profond, et l'ancien escalier qui permettait de traverser s'est effondré. Hors de question de faire demi-tour, vous allez faire un peu de rappel pour atteindre l'ouverture située en contrebas.

La paroi du gouffre est lisse, hormis ce qui reste de l'ancien escalier, qui forme une succession de plateformes juste assez larges pour y prendre appui. Si l'on représente ces plateformes dans une grille, elles sont placées une par rangée, et leurs bords droits suivent une diagonale de telle sorte que la ie plateforme s'étend d'une colonne inférieure ou égale à i, jusqu'à la colonne i incluse.

Lorsque vous êtes sur une plateforme, vous pouvez vous placer à n'importe quelle colonne le long de cette plateforme, et descendre en rappel jusqu'à toute plateforme qui passe par cette colonne. Vous partez de la première plateforme (la plus haute), et votre but est d'atteindre la dernière plateforme en effectuant le plus petit nombre de descentes en rappel possible.

L' illustration ci-dessous représente un exemple d'une telle paroi, et ses plateformes. On peut atteindre la dernière plateforme en 4 étapes, comme représenté par les flèches rouges.

Limites de temps et de mémoire (Python)

  • Temps : 0,5 s sur une machine à 1 GHz.
  • Mémoire : 8 000 ko.

Contraintes

  • 2 ≤ nbPlateformes ≤ 100 000

De plus, dans 40% des tests, on a nbPlateformes ≤ 300.

Entrée

La première ligne de l'entrée contient un entier : nbPlateformes.

Les nbPlateformes lignes suivantes décrivent les plateformes dans l'ordre, en partant de la plus haute, et contiennent chacune un entier entre 1 et le numéro de la plateforme inclus : la colonne de gauche de la plateforme.

Par exemple, si le 5e nombre est un 3, cela signifie que la cinquième plateforme en partant du haut s'étend de la colonne 3 à la colonne 5 (incluse).

Sortie

Vous devez afficher un entier sur la sortie : le nombre minimal de descentes en rappel nécessaires pour aller de la première à la dernière plateforme. S'il n'est pas possible d'atteindre la dernière plateforme, affichez -1.

Exemples

Exemple 1

entrée :

9
1
1
2
3
2
3
4
7
6

sortie :

4

Exemple 2

entrée :

6
1
2
1
4
5
4

sortie :

-1

Source : https://www.france-ioi.org/