No tag edit access

The problem statement has recently been changed. View the changes.

×
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-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/16/2021 20:20:47 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|