A. Group of Permutations
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ positive integers.

Can you partition this array into consecutive groups such that every group is a permutation of any size ?

A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[3,1,2,5,4]$$$ is a permutation, but $$$[1,2,1]$$$ is not a permutation (1 appears twice in the array) and $$$[2,1,4]$$$ is also not a permutation ($$$n=3$$$, but $$$4$$$ is in the array).

For example, if $$$a = [4,1,3,2,2,1,3,2,1]$$$ you can split it into $$$3$$$ groups : $$$([4,1,3,2] \ [2,1] \ [3,2,1])$$$. However the array $$$a = [4,1,3,2,3,1]$$$ can't be partitioned into groups of permutations.

Input

The first line of each test case contains one integer $$$n \ (1 \le n \le 2000)$$$ — the size of $$$a$$$

The second line contains $$$n$$$ positive integers $$$a_1, a_2, …,\ a_n \ (1 \le a_i \le 2000)$$$

Output

If there is a solution, print "YES". Otherwise, print "NO"

Examples
Input
9
4 1 3 2 2 1 3 2 1
Output
YES
Input
6
4 1 3 2 3 1
Output
NO