Vérifier si un tableau est triable par pile

Étant donné les nombres 1, 2, 3, ..., n dans un tableau d'ordre arbitraire, vous devez déterminer si ce tableau est triable par une pile. On dit que le tableau A est triable par pile s’il est possible, en utilisant une pile auxiliaire, d’obtenir un tableau B qui soit trié en ordre croissant lorsque l’algorithme se termine. Les opérations autorisées sont :

Retirer le premier élément de A et le pousser dans la pile.
Retirer l’élément au sommet de la pile et l’ajouter à la fin de B.

Si B se retrouve trié en ordre croissant, alors A est triable par pile.

Entrée

La première ligne de l’entrée contient un entier n (1 ≤ n ≤ ).

La ligne suivante contient n entiers séparés par des espaces (1 ≤ ≤ n).

Sortie

Le programme doit afficher Yes si A est triable par pile et No sinon.

Exemples

Entrée	Sortie
4 4 1 2 3	Yes
3 3 2 1	Yes
3 1 2 3	Yes
4 2 4 1 3	No

Explication

A = [4, 1, 2, 3], S = [], B = []

Opération 1: A = [1, 2, 3], S = [4], B = []
Opération 1: A = [2, 3], S = [4, 1], B = []
Opération 2: A = [2, 3], S = [4], B = [1]
Opération 1: A = [3], S = [4, 2], B = [1]
Opération 2: A = [3], S = [4], B = [1, 2]
Opération 1: A = [], S = [4, 3], B = [1, 2]
Opération 2: A = [], S = [4], B = [1, 2, 3]
Opération 2: A = [], S = [], B = [1, 2, 3, 4]

A = [3, 2, 1], S = [], B = []

Opération 1: A = [2, 1], S = [3], B = []
Opération 1: A = [1], S = [3, 2], B = []
Opération 1: A = [], S = [3, 2, 1], B = []
Opération 2: A = [], S = [3, 2], B = [1]
Opération 2: A = [], S = [3], B = [1, 2]
Opération 2: A = [], S = [], B = [1, 2, 3]

A = [1, 2, 3], S = [], B = []

Opération 1: A = [2, 3], S = [1], B = []
Opération 2: A = [2, 3], S = [], B = [1]
Opération 1: A = [3], S = [2], B = [1]
Opération 2: A = [3], S = [], B = [1, 2]
Opération 1: A = [], S = [3], B = [1, 2]
Opération 2: A = [], S = [], B = [1, 2, 3]

Il est impossible de trier [2, 4, 1, 3] par pile

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 10 MB