Croissance – Qualification 2014

Niveau 3

Énoncé

Joseph Marchand, surnommé Super Marchand par ses collègues, cherche à savoir si son réseau de tuyaux vérifie une certaine propriété.

On dit qu'un réseau de tuyaux conserve l'ordre s'il vérifie la propriété suivante : si l'on considère un nombre quelconque de plombiers placés sur le réseau, qu'on en choisit un qu'on numérote P1 et qu'on effectue un tour complet pour numéroter tous les autres dans leur ordre d'apparition (P2, …, Pk) et que chaque Pi emprunte le tuyau se trouvant sur sa case, alors en partant de la nouvelle position de P1 et en effectuant un tour complet, on parcourra tous les plombiers dans l'ordre de leur numérotation (ils pourront notamment se trouver sur la même case si leurs indices sont consécutifs).

On vous donne une liste de nombres représentant le nombre de cases que vous fait gagner chaque tuyau, écrivez une fonction qui renvoie 1 si le réseau de tuyaux conserve l'ordre et 0 sinon.

Entrée

L'entrée comprendra :

  • un nombre N, le nombre de tuyaux mesurés ;
  • sur la ligne suivante, N nombres L1 à LN représentant la distance que vous fait gagner chaque tuyau.

Sortie

Vous afficherez en sortie :

  • 1 si le réseau de tuyaux conserve l'ordre et 0 si ce n'est pas le cas.

Contraintes

  • 1 <= N <= 100 000
  • 0 <= Li < N

Contraintes d'exécution

Utilisation mémoire maximum
5000 kilo-octets
Temps d'exécution maximum
500 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
6
0 3 1 0 0 0
Exemple de sortie
0
Exemple d'entrée
5
3 2 1 2 2
Exemple de sortie
1