#956 Sorting a Sequence 3

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 either of the following operations zero or more times, in any order. Each operation uses one of the two choices.

Determine whether $A$ can be made sorted.

The input is given in the following format.

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

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

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

Sample 1

Input

3
2 3 1

Output

YES

Sample 2

Input

3
3 2 1

Output

NO