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
4 1 2 3 | Yes |
3
3 2 1 | Yes |
3
1 2 3 | Yes |
4
2 4 1 3 | 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