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[] = {1, 6, 3, 4, 5, 2, 7} ta có câu trả lời là Yes vì: ta chọn mảng con {3,4, 5} và đảo ngược để nhận được mảng A[]={1, 6, 5, 4, 3, 2, 7}, chọn tiếp mảng con {6, 5, 4, 3, 2} và đảo ngược ta nhận được mảng A[]={1, 2, 3, 4, 5, 6, 7}. 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