D. Gioconda
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While searching in the garbage cans, Jean found a sequence of $$$N$$$ positive integers. Because he has no use for this, he gifted it to Nicusor Gioconda, and gave him a challenge too.

Nicusor has to chose pairwise distinct substrings of length $$$2$$$ such that every index is taken at least once. If he will give a correct partitioning, he will get the ultimate prize: the magical chicken wing!

In this problem, we consider that a substring is a contiguous subset of indices $$$[i,i+1,\cdots j-1, j]$$$.

Because he is far better at singing than he is at solving problems, he asks for your help.

Input

First line will contain a single number $$$N$$$ ($$$1 \leq N \leq 10^5$$$) - the length of the sequence. The next line contains a sequence $$$A$$$ of $$$N$$$ positive values ($$$1 \leq A_i \leq 500$$$).

Output

The first line will contain a string that is either "YES" or "NO", that represents the existence of a correct partitioning.

Scoring
  • for 20 point it is guaranteed that $$$N \leq 20$$$
  • for the other 80 points we have $$$N \leq 10^5$$$
Examples
Input
5
1 2 1 2 3
Output
YES
Input
5
1 2 2 2 2
Output
NO
Note

For the first example, a valid partitioning is $$$[1,2], [2,1], [2,3]$$$ corresponding to the indices $$$[1,2], [2,3], [4,5]$$$.