H. Red Combo
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A fighting game just added a random character who only appeared in the show for two episodes. This character has $$$N$$$ skill moves, numbered $$$1$$$ to $$$N$$$.

Players found that performing moves in their natural order ($$$1, 2, 3, \dots, N$$$) creates a red combo, meaning their opponent couldn't escape. However, other permutations can also be red combos if they are generated by the following recursive process:

  1. Start with the base sequence: $$$[1, 2, 3, \dots, N]$$$.
  2. Cut the current sequence into two non-empty contiguous parts, $$$L$$$ and $$$R$$$.
  3. Rearrange the two parts: either $$$(L, R)$$$ or swap them to $$$(R, L)$$$.
  4. Recurse: repeat this process (starting from step 2) on $$$L$$$ and $$$R$$$ individually.

Given a permutation of the $$$N$$$ moves, determine if it is a red combo.

Input

The first line contains an integer $$$N$$$ ($$$1 \le N \le 10^6$$$) — the number of skill moves.

The second line contains $$$N$$$ distinct integers $$$p_1, p_2, \dots, p_N$$$ ($$$1 \le p_i \le N$$$) — the permutation of moves executed by the player.

Output

Print YES if the given permutation is a valid red combo, and NO otherwise.

Examples
Input
4
2 4 1 3
Output
NO
Input
4
1 3 4 2
Output
YES