Dãy đổi chiều theo quan hệ kề (Alternating Adjacent Comparisons)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy số nguyên $a_1,a_2,\ldots,a_n$.

Dãy được gọi là đổi chiều theo quan hệ kề nếu các quan hệ giữa hai phần tử kề liên tiếp luôn luân phiên giữa tăng và giảm. Cụ thể, với mọi $i$ thỏa $2\le i\le n-1$, phải có

Điều này đồng nghĩa với việc tại mỗi vị trí giữa, một trong hai mẫu sau phải xảy ra:

hoặc

Nếu có hai phần tử kề bằng nhau thì dãy không thỏa điều kiện. Với $n\le2$, không tồn tại vị trí giữa cần kiểm tra nên dãy được xem là thỏa điều kiện.

Hãy xác định dãy đã cho có đổi chiều theo quan hệ kề hay không.

Input

Dòng đầu chứa số nguyên $n$. Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$, cách nhau bởi dấu cách.

Output

In YES nếu dãy đổi chiều theo quan hệ kề; ngược lại in NO.

Subtask

Subtask 1 (100 điểm): $1\le n\le 2\cdot 10^5$; $|a_i|\le 10^9$.

Ví dụ

Input

6
1 4 2 5 3 6

Output

YES

Giải thích

Các quan hệ kề lần lượt là $<,>,<,>,<$ nên dấu so sánh luân phiên ở mọi bước.