#include <bits/stdc++.h>
using namespace std;
const int maxn = 30;
int d[5000][maxn];
int n, nin, nleaf;
int c[maxn];
int nbits[5000];
int main() {
  memset(d, 0, sizeof(d));
  ;
  nin = nleaf = 0;
  cin >> n;
  for (int i = 0; i < (n); i++) {
    int x;
    cin >> x;
    if (x == 1) {
      nleaf++;
    } else {
      c[nin++] = x;
    }
  }
  if (nin + 1 > nleaf) {
    cout << "NO" << endl;
    return 0;
  }
  for (int x = 1; x < 5000; x++) nbits[x] = nbits[x / 2] + x % 2;
  for (int i = 0; i <= nleaf; i++) d[0][i] |= (1 << i);
  for (unsigned int x = 1; x < (1 << nin); x++) {
    for (int k = 1; k <= nleaf; k++) {
      d[x][k] |= (d[x][k - 1] << 1);
      for (int i = 0; i < nin; i++) {
        if (!(x & (1 << i))) continue;
        unsigned int mask = x ^ (1 << i);
        unsigned int y = 0;
        do {
          int z = mask ^ y;
          int l = c[i] - nbits[y] - 1;
          if (l >= 0 && l <= k) {
            if (d[y][l] & (~3)) d[x][k] |= d[z][k - l] << 1;
          }
          y = ((y | (~mask)) + 1) & mask;
        } while (y);
      }
    }
  }
  int all = (1 << nin) - 1;
  if (d[all][nleaf] & 2) {
    cout << "YES" << endl;
    return 0;
  }
  cout << "NO" << endl;
  return 0;
}

### Prompt

Please formulate a Cpp solution to 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 maxn = 30;
int d[5000][maxn];
int n, nin, nleaf;
int c[maxn];
int nbits[5000];
int main() {
  memset(d, 0, sizeof(d));
  ;
  nin = nleaf = 0;
  cin >> n;
  for (int i = 0; i < (n); i++) {
    int x;
    cin >> x;
    if (x == 1) {
      nleaf++;
    } else {
      c[nin++] = x;
    }
  }
  if (nin + 1 > nleaf) {
    cout << "NO" << endl;
    return 0;
  }
  for (int x = 1; x < 5000; x++) nbits[x] = nbits[x / 2] + x % 2;
  for (int i = 0; i <= nleaf; i++) d[0][i] |= (1 << i);
  for (unsigned int x = 1; x < (1 << nin); x++) {
    for (int k = 1; k <= nleaf; k++) {
      d[x][k] |= (d[x][k - 1] << 1);
      for (int i = 0; i < nin; i++) {
        if (!(x & (1 << i))) continue;
        unsigned int mask = x ^ (1 << i);
        unsigned int y = 0;
        do {
          int z = mask ^ y;
          int l = c[i] - nbits[y] - 1;
          if (l >= 0 && l <= k) {
            if (d[y][l] & (~3)) d[x][k] |= d[z][k - l] << 1;
          }
          y = ((y | (~mask)) + 1) & mask;
        } while (y);
      }
    }
  }
  int all = (1 << nin) - 1;
  if (d[all][nleaf] & 2) {
    cout << "YES" << endl;
    return 0;
  }
  cout << "NO" << endl;
  return 0;
}

```