Rating changes for the last round are temporarily rolled back. They will be returned soon.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Guess the Tree

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIahub and Iahubina went to a picnic in a forest full of trees. Less than 5 minutes passed before Iahub remembered of trees from programming. Moreover, he invented a new problem and Iahubina has to solve it, otherwise Iahub won't give her the food.

Iahub asks Iahubina: can you build a rooted tree, such that

- each internal node (a node with at least one son) has at least two sons;
- node
*i*has*c*_{i}nodes in its subtree?

Iahubina has to guess the tree. Being a smart girl, she realized that it's possible no tree can follow Iahub's restrictions. In this way, Iahub will eat all the food. You need to help Iahubina: determine if there's at least one tree following Iahub's restrictions. The required tree must contain *n* nodes.

Input

The first line of the input contains integer *n* (1 ≤ *n* ≤ 24). Next line contains *n* positive integers: the *i*-th number represents *c*_{i} (1 ≤ *c*_{i} ≤ *n*).

Output

Output on the first line "YES" (without quotes) if there exist at least one tree following Iahub's restrictions, otherwise output "NO" (without quotes).

Examples

Input

4

1 1 1 4

Output

YES

Input

5

1 1 5 2 1

Output

NO

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/28/2020 21:25:01 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|