Kiểm tra mảng không giảm (Check a Nondecreasing Array)

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

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

Đề bài

Cho mảng số nguyên $a_0,a_1,\ldots,a_{n-1}$. Mảng được gọi là không giảm nếu

Các phần tử kề nhau được phép bằng nhau. Hãy kiểm tra mảng có thỏa điều kiện trên hay không. Không được sắp xếp lại mảng.

Input

Dòng đầu chứa $n$. Dòng thứ hai chứa $n$ số nguyên $a_i$.

Output

In YES nếu mảng không giảm; ngược lại in NO.

Subtask

Subtask 1 (20 điểm): $1\le n\le10$, $|a_i|\le10^3$.

Subtask 2 (30 điểm): $1\le n\le5000$, $|a_i|\le10^6$.

Subtask 3 (50 điểm): $1\le n\le2\cdot10^5$, $|a_i|\le10^9$.

Ví dụ

Input

6
-3 -3 0 4 4 10

Output

YES

Giải thích

Mọi cặp kề đều thỏa $a_{i-1}\le a_i$, kể cả các cặp có hai giá trị bằng nhau.