I. Line up
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Gunga have a permutation $$$p_1,p_2,\dots,p_n$$$ of length $$$n$$$ . He generates a sequence $$$a_1,a_2,\dots,a_n$$$ such that $$$a_i$$$ is either the minimum or the maximum number among $$$p_1,p_2,\dots,p_n$$$ . Given the sequence $$$a_1,a_2,\dots,a_n$$$ , can you recover the original permutation?

Input

The first line contains a single integer $$$n$$$ $$$(1\le n\le1000)$$$. The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1\le p_i\le n)$$$.

Output

If there is a possible solution for the permutation, print "YES", otherwise print "NO". (without quotes)

Examples
Input
5
2 2 3 1 5
Output
YES
Input
5
1 1 1 1 2
Output
NO
Note

In the first example, a possible permutation will be $$$2,3,1,4,5$$$.

In the second example, no possible permutation exists.