Input is a permutation of 1, 2, ..., n. For instance, 3, 2, 1. We are provided with a stack, and want to ask if we supply the numbers according to the permutation order, and at each step we can either
(i) get the next number from the supply, and output the number, or
(ii) get the next number from the supply, and push the number to the stack, or
(iii) pop from the stack, and output that number.
Can we obtain the output sequence as 1, 2, 3, ..., n.
So for the case of 3, 2, 1, the answer is YES (we push, push, output, then pop, pop).
Similarly, for the case of 1, 3, 2, the answer is YES, since we output, push, output, pop.
But for 2, 3, 1, the answer is NO.
Hint:
Our strategy could be as follows.
First, we try operation (iii).
If it is invalid, then we try operation (i).
If it cannot produce what we want, try operation (ii).
If we run out of the supply and the stack is not empty. The answer is NO.
There are multiple testcases in the input.
Each case contains two lines. First line contains a positive integer N indicating the length of permutation. The next line contains N distinct numbers (range 1~N) separated by a blank, which describe the given permutation.
The input is terminated by end-of-file (EOF).
Case 1: N <= 10
Case 2: N <= 100
Case 3: N <= 500
Case 4: N <= 1000
For each case, outupt a single line.
If the given permutation can be sorted by a stack, output "YES", otherwise, output "NO".