Statement

Timothy became fascinated with mathematical analysis when he was in second grade.

Since you will be dealing more with integers in algorithm competitions, you don't need a foundation in mathematical analysis to analyze the entire dense $\mathbb{R}$ but rather the discrete $\mathbb{Z}$, ensuring that the given data $x$ is definitely within the range of $-1\times 10^9 \leqslant x \leqslant 1\times 10^9$.

Let $\left\{x_n\right\}$ be a sequence (where $n \in \mathbb{N}$). For each $n$, define the distance between adjacent terms as $d_n = |x_n - x_{n+1}|$. If the sequence ${d_n}$ is (non-monotonically) decreasing ^[1], then ${x_n}$ is called an Incomplete Cauchy sequence. For example, the general formula for the sequence $\left\{ x_n \right\}$ is $x_n=-n, n\in \mathbb{N}$, that is, $\left\{ x_n \right\}=[-1,-2,-3,\cdots,-n]$ is an Incomplete Cauchy sequence; an array of the form $[1,100,50,75,75,75,75,\cdots,75]$ is also an Incomplete Cauchy sequence; whereas $[1,100,300,300,300,\cdots,300]$ is not, because $d_1=99, d_2=100, d_3=200$ does not satisfy the above definition.

Given an array $a$ of length $n$, determine whether this array can be a continuous subsequence of an Incomplete Cauchy sequence ^[2].

Input

The first line contains an integer $n$ representing the length of the array, where $3\leqslant n\leqslant 2\times 10^5$.

The second line contains $n$ integers separated by spaces, representing each element $a_i$ in the array $a$, where $-1\times 10^9 \leqslant a_i\leqslant 1\times 10^9$.

Output

If the array is a possible continuous subsequence of an Incomplete Cauchy sequence, output Yes. Otherwise, output No. The output is not case-sensitive. For example, YES and yEs are both considered as Yes.

Samples

3
-1 -2 -3

Yes

5
1 100 50 75 75

Yes

5
1 100 300 300 300

No