Verificar si un array es stack-sortable
Dado un conjunto de números 1, 2, 3, ..., n en un orden arbitrario, se te pide determinar si el array dado es stack-sortable. Decimos que un array A es stack-sortable si es posible obtener un array B usando una pila auxiliar de modo que, al terminar el algoritmo, B quede ordenado en orden ascendente. Las operaciones permitidas son:
Quitar el primer elemento de
Ay colocarlo en la pila.Quitar el elemento superior de la pila y añadirlo al final de
B.
Si al finalizar B está ordenado de forma ascendente, entonces A es stack-sortable.
Entrada
La primera línea de la entrada contiene un único entero n (1 ≤ n ≤ ).
La siguiente línea contiene n enteros separados por espacios (1 ≤ ≤ n).
Salida
El programa debe imprimir Yes si A es stack-sortable y No en caso contrario.
Ejemplos
Entrada | Salida |
|---|---|
4 | Yes |
3 | Yes |
3 | Yes |
4 | No |
Explicación
A = [4, 1, 2, 3], S = [], B = []
Operation 1:
A = [1, 2, 3],S = [4],B = []Operation 1:
A = [2, 3],S = [4, 1],B = []Operation 2:
A = [2, 3],S = [4],B = [1]Operation 1:
A = [3],S = [4, 2],B = [1]Operation 2:
A = [3],S = [4],B = [1, 2]Operation 1:
A = [],S = [4, 3],B = [1, 2]Operation 2:
A = [],S = [4],B = [1, 2, 3]Operation 2:
A = [],S = [],B = [1, 2, 3, 4]
A = [3, 2, 1], S = [], B = []
Operation 1:
A = [2, 1],S = [3],B = []Operation 1:
A = [1],S = [3, 2],B = []Operation 1:
A = [],S = [3, 2, 1],B = []Operation 2:
A = [],S = [3, 2],B = [1]Operation 2:
A = [],S = [3],B = [1, 2]Operation 2:
A = [],S = [],B = [1, 2, 3]
A = [1, 2, 3], S = [], B = []
Operation 1:
A = [2, 3],S = [1],B = []Operation 2:
A = [2, 3],S = [],B = [1]Operation 1:
A = [3],S = [2],B = [1]Operation 2:
A = [3],S = [],B = [1, 2]Operation 1:
A = [],S = [3],B = [1, 2]Operation 2:
A = [],S = [],B = [1, 2, 3]
It’s impossible to stack-sort the array [2, 4, 1, 3]
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 10 MB