The 2Dgyptians are a race of 2-dimensional humans who love building big structures. Specifically, they are trying build a big triangle to honour their leader. The do this, they build up bricks layer-by-layer. The bricks are organised in piles, and they want the piles to be such that each pile has exactly enough bricks to build each layer of the triangle. This means the piles should be ~k,k-1,\dots,2,1~ for some integer ~k~.

The piles are currently in a random, messed up state! The 2Dgyptians are able to arbitrarily merge, split, and rearrange the piles as they like, but the total number must be maintained. Is it possible to rearrange them into the desired format to begin building the triangle layers?

Input

The first line contains a single integer ~n~ (~1 \leq n \leq 10^5~), the number of brick piles that already exist.

The next line contains ~n~ space-separated integer ~x_i~ (~1 \leq x_i \leq 10^5~), the amount of bricks in the ~i~th pile.

Output

If it is possible to create piles corresponding to rows of some triangle, i.e. piles of size ~k,\dots,2,1~ for some integer ~k~, output "YES". This can be done by performaing the following operations on piles:

• Rearranging (swapping any pairs of piles)
• Splitting (turning a pile into multiple piles where the sum of the resulting piles is the same as the previous pile)
• Merging (adding up multiple piles to create a single pile)

If it is not possible, output "NO".

Example

Input 1

4
1 5 3 1

Output 1

YES

It is possible to rearrange these piles into ~4,3,2,1~.

For instance, by swapping we can obtain ~5,3,1,1~. We can then split the ~5~ into ~4,1~ and swap to obtain ~4,3,1,1,1~. We can then merge some of the ones to obtain ~4,3,2,1~.

Input 2

5
1 2 7 1 8

Output 2

NO

We can create ~5,4,3,2,1~, but there would be some bricks leftover. We can create ~6,5,4,3,1~, but there are not enough to complete this as the ~2~ is missing.

Input 3

1
1

Output 3

YES

A pyramid with one row of one brick is valid.