Determine whether an array is monotonic: entirely non-decreasing or entirely non-increasing.

Input

The first line contains \(n\). The second line contains \(n\) integers.

The input satisfies:

• \(1 <= n <= 10^5\)

Output

Print YES if the array is monotonic; otherwise print NO.

Example

Input

4
5 3 1 -4

Output

YES