Given an array $A$ consisting of $n$ integer elements, check if $A$ is a bitonic sequence.

A sequence is called a bitonic sequence if there exists an index $i$ such that:

• For all $j < i$, $A_j < A_{j + 1}$.
• For all $j > i$, $A_j < A_{j-1}$.

Input

• The first line contains an integer $n$.
• The second line contains $n$ integers $A_i$.

Output

• If $A$ is a bitonic sequence, print YES, otherwise print NO.

Constraints

• $1 \le n \le 10^5$.
• $1 \le A_i \le 10^9$.

Example

Input:

4
1 4 10 2

Output:

YES