#include <bits/stdc++.h>
using namespace std;
const int oo = 999999999;
const double PI = 3.1415931;
const double eps = 1e-9;
const int maxN = 24 + 10;
int dp[1 << 15];
int a[maxN], n;
int ones, noneOne;
bool ans = false;
void go(int pos, int leaveNumber, int mask) {
  if (ans) return;
  if (!((1 << pos) & mask) && a[pos] != 1) return;
  if (a[pos] == 1) {
    if (leaveNumber == 0 && __builtin_popcount(mask) == noneOne) ans = true;
    return;
  }
  int mask2 = mask ^ ((1 << (noneOne)) - 1);
  int cnt = 1;
  for (int i = mask2; i >= 0 && cnt; i = mask2 & (i - 1)) {
    if (i == 0) cnt--;
    bool flag = true;
    int sum = dp[i];
    int need = a[pos] - 1;
    if (sum + leaveNumber < need) continue;
    if (sum > need) continue;
    int leaveUsed = need - sum;
    if ((leaveUsed + (__builtin_popcount(i))) < 2) continue;
    go(pos + 1, leaveNumber - leaveUsed, mask | i);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] == 1) ones++;
  }
  if (n == 1 && a[0] == 1) {
    cout << "YES";
    return 0;
  }
  noneOne = n - ones;
  if (ones < n / 2 || noneOne == 0) {
    cout << "NO\n";
    return 0;
  }
  sort(a, a + n, greater<int>());
  for (int i = 0; i < (1 << noneOne); i++) {
    for (int j = 0; j < noneOne; j++) {
      if (i & 1 << j) {
        dp[i] += a[j];
      }
    }
  }
  go(0, ones, 1);
  if (ans) {
    cout << "YES\n";
  } else
    cout << "NO\n";
  return 0;
}

### Prompt

In Cpp, your task is to solve the following problem:

Iahub 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 ci 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 ci (1 ≤ ci ≤ 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int oo = 999999999;
const double PI = 3.1415931;
const double eps = 1e-9;
const int maxN = 24 + 10;
int dp[1 << 15];
int a[maxN], n;
int ones, noneOne;
bool ans = false;
void go(int pos, int leaveNumber, int mask) {
  if (ans) return;
  if (!((1 << pos) & mask) && a[pos] != 1) return;
  if (a[pos] == 1) {
    if (leaveNumber == 0 && __builtin_popcount(mask) == noneOne) ans = true;
    return;
  }
  int mask2 = mask ^ ((1 << (noneOne)) - 1);
  int cnt = 1;
  for (int i = mask2; i >= 0 && cnt; i = mask2 & (i - 1)) {
    if (i == 0) cnt--;
    bool flag = true;
    int sum = dp[i];
    int need = a[pos] - 1;
    if (sum + leaveNumber < need) continue;
    if (sum > need) continue;
    int leaveUsed = need - sum;
    if ((leaveUsed + (__builtin_popcount(i))) < 2) continue;
    go(pos + 1, leaveNumber - leaveUsed, mask | i);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] == 1) ones++;
  }
  if (n == 1 && a[0] == 1) {
    cout << "YES";
    return 0;
  }
  noneOne = n - ones;
  if (ones < n / 2 || noneOne == 0) {
    cout << "NO\n";
    return 0;
  }
  sort(a, a + n, greater<int>());
  for (int i = 0; i < (1 << noneOne); i++) {
    for (int j = 0; j < noneOne; j++) {
      if (i & 1 << j) {
        dp[i] += a[j];
      }
    }
  }
  go(0, ones, 1);
  if (ans) {
    cout << "YES\n";
  } else
    cout << "NO\n";
  return 0;
}

```