#include <bits/stdc++.h>
using namespace std;
vector<int> c;
int dp[12][1 << 12][14];
int sum[1 << 12];
int bits[1 << 12];
int f(int idx, int mask, int leaf) {
  if (idx == c.size()) {
    if (mask == 0 && leaf == 0) return 1;
    return 0;
  }
  int &ref = dp[idx][mask][leaf];
  if (ref != -1) return ref;
  ref = 0;
  if (c[idx] - 1 <= leaf && c[idx] - 1 >= 2) {
    ref |= f(idx + 1, mask, leaf - c[idx] + 1);
  }
  for (int mask2 = mask; mask2 > 0; mask2 = mask & (mask2 - 1)) {
    if (c[idx] - 1 >= sum[mask2] && leaf >= c[idx] - 1 - sum[mask2] &&
        bits[mask2] + c[idx] - sum[mask2] - 1 >= 2) {
      ref |= f(idx + 1, mask ^ mask2, leaf - c[idx] + sum[mask2] + 1);
    }
  }
  return ref;
}
int main() {
  int n, x, leaf;
  cin >> n;
  leaf = 0;
  for (int i = 0; i < n; i++) {
    cin >> x;
    if (x == 1)
      leaf++;
    else
      c.push_back(x);
  }
  if (leaf < (n + 1) / 2) {
    cout << "NO" << endl;
    return 0;
  }
  if (n == 1) {
    cout << "YES" << endl;
    return 0;
  }
  sort(c.begin(), c.end(), greater<int>());
  memset(sum, 0, sizeof sum);
  memset(bits, 0, sizeof bits);
  for (int mask = (1 << c.size()) - 1; mask >= 0; mask--) {
    bits[mask] = sum[mask] = 0;
    for (int i = 0; i < c.size(); i++) {
      if (mask & (1 << i)) {
        bits[mask]++;
        sum[mask] += c[i];
      }
    }
  }
  memset(dp, -1, sizeof dp);
  string out[] = {"NO", "YES"};
  cout << out[f(0, (1 << c.size()) - 1 - 1, leaf)] << endl;
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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;
vector<int> c;
int dp[12][1 << 12][14];
int sum[1 << 12];
int bits[1 << 12];
int f(int idx, int mask, int leaf) {
  if (idx == c.size()) {
    if (mask == 0 && leaf == 0) return 1;
    return 0;
  }
  int &ref = dp[idx][mask][leaf];
  if (ref != -1) return ref;
  ref = 0;
  if (c[idx] - 1 <= leaf && c[idx] - 1 >= 2) {
    ref |= f(idx + 1, mask, leaf - c[idx] + 1);
  }
  for (int mask2 = mask; mask2 > 0; mask2 = mask & (mask2 - 1)) {
    if (c[idx] - 1 >= sum[mask2] && leaf >= c[idx] - 1 - sum[mask2] &&
        bits[mask2] + c[idx] - sum[mask2] - 1 >= 2) {
      ref |= f(idx + 1, mask ^ mask2, leaf - c[idx] + sum[mask2] + 1);
    }
  }
  return ref;
}
int main() {
  int n, x, leaf;
  cin >> n;
  leaf = 0;
  for (int i = 0; i < n; i++) {
    cin >> x;
    if (x == 1)
      leaf++;
    else
      c.push_back(x);
  }
  if (leaf < (n + 1) / 2) {
    cout << "NO" << endl;
    return 0;
  }
  if (n == 1) {
    cout << "YES" << endl;
    return 0;
  }
  sort(c.begin(), c.end(), greater<int>());
  memset(sum, 0, sizeof sum);
  memset(bits, 0, sizeof bits);
  for (int mask = (1 << c.size()) - 1; mask >= 0; mask--) {
    bits[mask] = sum[mask] = 0;
    for (int i = 0; i < c.size(); i++) {
      if (mask & (1 << i)) {
        bits[mask]++;
        sum[mask] += c[i];
      }
    }
  }
  memset(dp, -1, sizeof dp);
  string out[] = {"NO", "YES"};
  cout << out[f(0, (1 << c.size()) - 1 - 1, leaf)] << endl;
  return 0;
}

```