Check if an array is stack sortable
Given the numbers
1, 2, 3, ..., n as an array in arbitrary order, you are asked to check if the given array is stack-sortable. The array A is stack-sortable if it’s possible to obtain an array B using an auxiliary stack and B would be sorted in increasing order by the end of the algorithm execution. The allowed operations are:- Remove the first element from
Aand push it onto the stack.
- Remove the top element from the stack and append it to the end of
B.
If
B is sorted in increasing order, then A is stack-sortable.Input
The first line of the input contains a single integer
n (1 ≤ n ≤ ).The next line contains
n space-separated integers (1 ≤ ≤ n).Output
The program should print
Yes if A is stack-sortable and No otherwise.Examples
Input | Output |
4
4 1 2 3 | Yes |
3
3 2 1 | Yes |
3
1 2 3 | Yes |
4
2 4 1 3 | No |
Explanation
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