#955 Sorting a Sequence 2

Statement

Statement language

A sequence $A$ of length $N$ is sorted if $A_i \leq A_{i+1}$ for every $1 \leq i < N$ .

You may perform the following operation zero or more times: choose an integer $p$ with $1 \leq p < N$ and swap $A_p$ and $A_{p +}$ . Determine whether can be made sorted.

Input

The input is given in the following format.

$N$ $A_1\ A_2\ \cdots\ A_N$

Output

Print YES if the sequence can be made sorted, and NO otherwise.

Constraints

$1 \leq N \leq 100$ .
$-10^9\leq A_i\leq10^9$ ().

Subtasks

#	Score	Constraints
1	10	$N\leq3$ .
2	20	At most two distinct values occur in $A$ .
3	30	All elements of $A$ are distinct.
4	40	No additional constraints.

Samples

Input

3
3 1 2

Output

YES