Rieles

Hay una famosa estación de tren en PopPush City. El país es increíblemente montañoso. La estación fue construida en el siglo pasado. Desafortunadamente, en ese tiempo, los fondos eran muy limitados, por lo que solamente fue posible establecer una pista sobre la superficie. Por otra parte, resultó que la estación sólo podía ser como un callejón sin salida (ver imagen) y debido a la falta de espacio disponible sólo podía tener una pista.

La tradición local indica que cada tren que llega desde la dirección A continúa en dirección B con los vagones organizados de alguna manera. Supongamos que el tren que llega desde la dirección A tiene N <= 1000 vagones numerados en orden creciente 1,2, …, N. El jefe de organización de trenes debe saber si es posible ordenar los vagones, continuando en la dirección B para que su orden sea a₁, a₂, a_n. Ayúdalo escribiendo un programa que diga si es posible obtener el orden requerido de vagones.

Puedes asumir que los vagones pueden ser desconectados individualmente del tren antes de que entren a la estación, y, que pueden moverse por su cuenta hasta que estén en la pista de la dirección B. Puedes también suponer que en cualquier momento pueden ser localizados tantos vagones, como sea necesario, en la estación. Pero una vez que un vagón ha entrado en la estación no puede salir por la pista de la dirección A y una vez que ha dejado la estación en la dirección B no puede volver a entrar.