Module: Práctica de pila

Requerido para determinar si una secuencia de números se puede ordenar usando una pila.

Un tren ha llegado al callejón sin salida de la vía 1 (ver imagen). Está permitido desenganchar uno o varios primeros vagones del tren a la vez y llevarlos a un callejón sin salida (si lo desea, puede incluso llevar todo el tren a un callejón sin salida a la vez). Después de eso, lleve algunos de los vagones al lado de la vía 2. Luego puede llevar algunos vagones más al callejón sin salida y otra vez transportar parte de los vagones al lado de la vía 2. Y así sucesivamente, para que cada vagón conduce desde la vía 1 hasta el callejón sin salida solo una vez, y luego una vez salió del callejón sin salida en la vía 2. Está prohibido ingresar al callejón sin salida desde la vía 2 o salir del callejón sin salida en la vía 1. No puedes pasar de la ruta 1 a la ruta 2 sin entrar en un callejón sin salida.

Se sabe en qué orden van inicialmente los vagones del tren. Se requiere, mediante las operaciones indicadas, hacer que los vagones del tren vayan en orden (primero el primero, luego el segundo, etc., contados desde la cabeza del tren que circula por la vía 2 alejándose del callejón sin salida). Escribe un programa para determinar si se puede hacer.

 

Entrada
Introduzca el número N — el número de vagones en el tren (\(1<=N<=2000\)). A continuación están los números de vagón en orden desde la cabeza del tren que viaja en la vía 1 hacia el callejón sin salida. Los autos están numerados con números naturales desde 1 a N, cada uno de los cuales ocurre exactamente una vez.

 

Salida
¿Es posible hacer que los vagones vayan en orden de 1 a N, contando desde la cabeza del tren, cuando el tren toma la vía 2 desde el callejón sin salida?  Si es posible, muestre un mensaje YES. Si no es posible, escriba NO.