Croissance – Qualification 2014

É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 P₁ et qu'on effectue un tour complet pour numéroter tous les autres dans leur ordre d'apparition (P₂, …, P_k) et que chaque P_i emprunte le tuyau se trouvant sur sa case, alors en partant de la nouvelle position de P₁ 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 L₁ à L_N 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 <= L_i < N