Cho mảng A[] gồm N số và thực hiện các thao tác theo nguyên tắc dưới đây: Ta chọn một mảng con sao cho phần tử ở giữa của mảng con cũng là phần tử ở giữa của mảng A[] (trong trường hợp N lẻ). Đảo ngược mảng con đã chọn trong mảng A[]. Ta được phép chọn mảng con và phép đảo ngược mảng con bao nhiêu lần tùy ý. Ví dụ với mảng A[] = ta có câu trả lời là Yes vì: ta chọn mảng con và đảo ngược để nhận được mảng A[]=, chọn tiếp mảng con và đảo ngược ta nhận được mảng A[]=. Hãy cho biết ta có thể sắp xếp được mảng A[] bằng cách thực hiện các thao tác kể trên hay không?

Input Format

Dòng 1 chứa số nguyên dương N là số lẻ. Dòng 2 chứa N số nguyên của mảng A[]. (1<=N<=10^6; 0<=A[i]<=10^9)

Constraints

.

Output Format

In ra YES hoặc NO là đáp án của bài toán.

Ví dụ:

Dữ liệu vào

7
1 6 3 4 5 2 7

Dữ liệu ra

YES