Jamie is interested in sorting a number of boxes, each labelled with a distinct integer. He really loves even numbers and the number 2, so he is willing to swap any two boxes that are exactly two places apart (a[i] and a[i+2] for any i). He has nothing better to do, so he is happy to repeat this operation as many times as necessary, but wants to know if he can get the line of boxes into an overall increasing sorted order by doing it, so he doesn't have to waste his time if its impossible. Can you let him know?

Input

The first line consists of a single integer ~n~ ~(1 \leq n \leq 10^5)~, the number of boxes.

The next line consists of ~n~ space-separated integers ~a_i~ ~(0 \leq a_i \leq 10^9)~, the values on each of the boxes. There are no two boxes that share the same number.

Output

If it is possible to sort the boxes by only swapping boxes with the box two places away from them, output Yes, otherwise output No.

Example

Input 1

4
3 2 1 4

Output 1

Yes

Swapping the first and third elements immediately gives 1 2 3 4.

Input 2

4
2 1 4 3

Output 2

No

No matter how many swaps we perform, reaching sorted order is impossible.