Croissance – Qualification 2014

Level 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

Runtime constraints

Maximum memory usage
5000 kilobytes
Maximum execution time
500 milliseconds

Input/output samples

Sample input
6
0 3 1 0 0 0
Sample output
0
Sample input
5
3 2 1 2 2
Sample output
1

Submit your solution

You have to register or log in to be able to submit your solution.