Dãy đổi chiều theo quan hệ kề (Alternating Adjacent Comparisons)

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

Given an integer sequence $a_1,a_2,\ldots,a_n$.

The sequence has alternating adjacent comparisons when the relation between consecutive elements alternates strictly between increasing and decreasing. Formally, for every $i$ with $2\le i\le n-1$,

Equivalently, every interior position must satisfy exactly one of

or

Equal adjacent values violate the condition. For $n\le2$, there is no interior position to check, so the sequence is considered valid.

Determine whether the given sequence satisfies the condition.

Input

The first line contains integer $n$. The second line contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$.

Output

Print YES if the sequence has alternating adjacent comparisons; otherwise print NO.

Subtasks

Subtask 1 (100 points): $1\le n\le 2\cdot 10^5$; $|a_i|\le 10^9$.

Example

Input

6
1 4 2 5 3 6

Output

YES

Explanation

The adjacent relations are $<,>,<,>,<$, so the comparison direction alternates at every step.