Triple Sort

Time limit1sMemory limit1024 MB

Summary

Given a permutation of 1 to N, decide whether repeatedly reversing any three consecutive elements can sort it into increasing order.

Level: Medium6 of 10
Topics: Math, Combinatorics, Greedy, Implementation
Solved: No attempts yet

Problem

After taking an algorithms class, Yoon was so impressed that he decided to invent his own sorting algorithm. His algorithm, "Triple Sort," works as follows.

Pick any three elements at consecutive positions in the array.
Reverse the order of the three elements. For example, if the three elements are $a, b, c$ in that order, after reversing they become $c, b, a$ .
Repeat the process until the array is sorted in increasing order.

Yoon then realized that Triple Sort cannot sort every array, and he was disappointed. Given an array containing each integer from $1$ to $N$ exactly once, write a program to determine whether Triple Sort can sort it.

Input

The first line gives an integer $N$ , the size of the array.

The second line gives the elements of the array in order, separated by spaces.

Output

Print YES if Triple Sort can sort the given array in increasing order, and NO otherwise.

Constraints

$3\leq N \leq 300,000$

Each integer from $1$ to $N$ appears exactly once in the given array.

Examples2

Example 1
Input
```
5
1 4 5 2 3
```
Expected output
```
YES
```
Example 2
Input
```
5
3 1 5 2 4
```
Expected output
```
NO
```