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 = `, `B = []`
1. Operation 1: `A = [2, 3]`, `S = [4, 1]`, `B = []`
1. Operation 2: `A = [2, 3]`, `S = `, `B = `
1. Operation 1: `A = `, `S = [4, 2]`, `B = `
1. Operation 2: `A = `, `S = `, `B = [1, 2]`
1. Operation 1: `A = []`, `S = [4, 3]`, `B = [1, 2]`
1. Operation 2: `A = []`, `S = `, `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 = `, `B = []`
1. Operation 1: `A = `, `S = [3, 2]`, `B = []`
1. Operation 1: `A = []`, `S = [3, 2, 1]`, `B = []`
1. Operation 2: `A = []`, `S = [3, 2]`, `B = `
1. Operation 2: `A = []`, `S = `, `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 = `, `B = []`
1. Operation 2: `A = [2, 3]`, `S = []`, `B = `
1. Operation 1: `A = `, `S = `, `B = `
1. Operation 2: `A = `, `S = []`, `B = [1, 2]`
1. Operation 1: `A = []`, `S = `, `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