Algorithms and Data Structures

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:
  1. Remove the first element from A and push it onto the stack.
  1. 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 = []
  1. Operation 1: A = [1, 2, 3], S = [4], B = []
  1. Operation 1: A = [2, 3], S = [4, 1], B = []
  1. Operation 2: A = [2, 3], S = [4], B = [1]
  1. Operation 1: A = [3], S = [4, 2], B = [1]
  1. Operation 2: A = [3], S = [4], B = [1, 2]
  1. Operation 1: A = [], S = [4, 3], B = [1, 2]
  1. Operation 2: A = [], S = [4], B = [1, 2, 3]
  1. Operation 2: A = [], S = [], B = [1, 2, 3, 4]
A = [3, 2, 1], S = [], B = []
  1. Operation 1: A = [2, 1], S = [3], B = []
  1. Operation 1: A = [1], S = [3, 2], B = []
  1. Operation 1: A = [], S = [3, 2, 1], B = []
  1. Operation 2: A = [], S = [3, 2], B = [1]
  1. Operation 2: A = [], S = [3], B = [1, 2]
  1. Operation 2: A = [], S = [], B = [1, 2, 3]
A = [1, 2, 3], S = [], B = []
  1. Operation 1: A = [2, 3], S = [1], B = []
  1. Operation 2: A = [2, 3], S = [], B = [1]
  1. Operation 1: A = [3], S = [2], B = [1]
  1. Operation 2: A = [3], S = [], B = [1, 2]
  1. Operation 1: A = [], S = [3], B = [1, 2]
  1. Operation 2: A = [], S = [], B = [1, 2, 3]
It’s impossible to stack-sort the array [2, 4, 1, 3]
 

Constraints

Time limit: 0.4 seconds

Memory limit: 512 MB

Output limit: 10 MB

To check your solution you need to sign in
Sign in to continue