Module: Prática de pilha

Necessário para determinar se uma sequência de números pode ser classificada usando uma pilha.

Um trem chegou ao beco sem saída da linha 1 (veja a figura). É permitido desenganchar um ou vários primeiros vagões do trem de uma só vez e trazê-los para um beco sem saída (se desejar, você pode até mesmo levar o trem inteiro para um beco sem saída de uma vez). Depois disso, leve alguns dos vagões para o lado da pista 2. Então você pode trazer mais alguns vagões para o beco sem saída e novamente transportar parte dos vagões para o lado da pista 2. E assim por diante, para que cada vagão dirige da pista 1 para o beco sem saída apenas uma vez e, em seguida, sai do beco sem saída na pista 2. É proibido entrar no beco sem saída da pista 2 ou sair do beco sem saída na pista 1. Você não pode ir do caminho 1 para o caminho 2 sem entrar em um beco sem saída.

Sabe-se em que ordem os vagões vão inicialmente. É necessário, usando as operações indicadas, fazer os vagões andarem em ordem (primeiro o primeiro, depois o segundo, etc., contando a partir da cabeceira do trem que percorre a linha 2 a partir do beco sem saída). Escreva um programa para determinar se isso pode ser feito.

 

Entrada
Digite o número N — o número de vagões no trem (\(1<=N<=2000\)). Em seguida, estão os números dos vagões em ordem, do início do trem que viaja na linha 1 em direção ao beco sem saída. Os carros são numerados com números naturais de 1 a N, cada um ocorrendo exatamente uma vez.

 

Saída
É possível fazer os vagões irem em ordem de 1 a N, contando da cabeceira do trem, quando o trem pega o trilho 2 do beco sem saída?  Se possível, exiba a mensagem SIM. Se não for possível, imprima NÃO.