Dãy nón

Giới hạn thời gian: 1000 ms Giới hạn bộ nhớ: 256 MB Cho mảng A gồm n phần tử nguyên, kiểm tra xem A có phải là dãy nón không?

Một dãy được gọi là dãy nón nếu tồn tại chỉ số i sao cho:

Với mọi j < i thì A j < A j + 1 . Với mọi j > i thì A j < A j - 1

Input

Dòng đầu tiên gồm số nguyên n . Dòng thứ hai gồm n số nguyên A i .

Output

Nếu A là dãy nón, in ra YES, ngược lại in ra NO. Điều kiện 1 ≤ n ≤ 10 5 . 1 ≤ A i ≤ 10 9 .

Ví dụ

Input:

4
1 4 10 2

Output:

YES