#include <bits/stdc++.h>
using namespace std;
int n, m;
int b[32];
int *c;
int btree[1 << 14][14];
int bfor[1 << 14][14][2];
int tree(int ma, int le);
int forest(int ma, int le, int ml = 2) {
  int pm = 0;
  if (ml == 2) pm = 1;
  if (bfor[ma][le][pm] != -1) return bfor[ma][le][pm];
  if (ma == (1LL << m) - 1) {
    if (le >= ml) return 1;
    return 0;
  }
  if (ml <= 1) {
    if (tree(ma, le)) {
      bfor[ma][le][pm] = 1;
      return 1;
    }
  }
  int i;
  for (i = m - 1; i >= 0; --i) {
    if (!(ma & (1 << i))) {
      break;
    }
  }
  int nma = 0;
  for (int sma = 0; sma < (1 << i); ++sma) {
    int mm = (ma & sma);
    nma = (ma | sma | (1 << i));
    for (int l = 0; l <= le; ++l) {
      if (tree((1LL << m) - 1 - sma - (1 << i) + mm, l)) {
        if (forest(nma, le - l, ml - 1)) {
          bfor[ma][le][pm] = 1;
          break;
        }
      }
    }
  }
  if (bfor[ma][le][pm] != 1) bfor[ma][le][pm] = 0;
  return bfor[ma][le][pm];
}
int tree(int ma, int le) {
  if (btree[ma][le] != -1) return btree[ma][le];
  if (ma == (1LL << m) - 1) {
    if (le == 1) return 1;
    return 0;
  }
  int fr = le;
  int mf = 0;
  int fi = 0;
  for (int i = 0; i < m; ++i) {
    if (!((1 << i) & ma)) {
      ++fr;
      if (c[i] > mf) {
        mf = c[i];
        fi = i;
      }
    }
  }
  if (mf != fr) {
    btree[ma][le] = 0;
    return btree[ma][le];
  }
  int nm = ma;
  nm = (nm | (1 << fi));
  btree[ma][le] = forest(nm, le);
  return btree[ma][le];
}
int main() {
  scanf("%d", &n);
  c = b;
  for (int i = 0; i < n; i++) {
    scanf("%d", &c[i]);
  }
  if (n == 1) {
    if (c[0] == 1)
      printf("YES\n");
    else
      printf("NO\n");
    return 0;
  }
  sort(c, c + n);
  if (c[n - 1] != n) {
    printf("NO\n");
    return 0;
  }
  int le = 0;
  while (c[0] == 1 && le < n) {
    ++le;
    ++c;
  }
  m = n - le;
  if (m > 13) {
    printf("NO\n");
    return 0;
  }
  memset(btree, -1, sizeof(btree));
  memset(bfor, -1, sizeof(bfor));
  if (tree(0, le)) {
    printf("YES\n");
    return 0;
  }
  printf("NO\n");
  return 0;
}

### Prompt

Create a solution in Cpp for 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;
int n, m;
int b[32];
int *c;
int btree[1 << 14][14];
int bfor[1 << 14][14][2];
int tree(int ma, int le);
int forest(int ma, int le, int ml = 2) {
  int pm = 0;
  if (ml == 2) pm = 1;
  if (bfor[ma][le][pm] != -1) return bfor[ma][le][pm];
  if (ma == (1LL << m) - 1) {
    if (le >= ml) return 1;
    return 0;
  }
  if (ml <= 1) {
    if (tree(ma, le)) {
      bfor[ma][le][pm] = 1;
      return 1;
    }
  }
  int i;
  for (i = m - 1; i >= 0; --i) {
    if (!(ma & (1 << i))) {
      break;
    }
  }
  int nma = 0;
  for (int sma = 0; sma < (1 << i); ++sma) {
    int mm = (ma & sma);
    nma = (ma | sma | (1 << i));
    for (int l = 0; l <= le; ++l) {
      if (tree((1LL << m) - 1 - sma - (1 << i) + mm, l)) {
        if (forest(nma, le - l, ml - 1)) {
          bfor[ma][le][pm] = 1;
          break;
        }
      }
    }
  }
  if (bfor[ma][le][pm] != 1) bfor[ma][le][pm] = 0;
  return bfor[ma][le][pm];
}
int tree(int ma, int le) {
  if (btree[ma][le] != -1) return btree[ma][le];
  if (ma == (1LL << m) - 1) {
    if (le == 1) return 1;
    return 0;
  }
  int fr = le;
  int mf = 0;
  int fi = 0;
  for (int i = 0; i < m; ++i) {
    if (!((1 << i) & ma)) {
      ++fr;
      if (c[i] > mf) {
        mf = c[i];
        fi = i;
      }
    }
  }
  if (mf != fr) {
    btree[ma][le] = 0;
    return btree[ma][le];
  }
  int nm = ma;
  nm = (nm | (1 << fi));
  btree[ma][le] = forest(nm, le);
  return btree[ma][le];
}
int main() {
  scanf("%d", &n);
  c = b;
  for (int i = 0; i < n; i++) {
    scanf("%d", &c[i]);
  }
  if (n == 1) {
    if (c[0] == 1)
      printf("YES\n");
    else
      printf("NO\n");
    return 0;
  }
  sort(c, c + n);
  if (c[n - 1] != n) {
    printf("NO\n");
    return 0;
  }
  int le = 0;
  while (c[0] == 1 && le < n) {
    ++le;
    ++c;
  }
  m = n - le;
  if (m > 13) {
    printf("NO\n");
    return 0;
  }
  memset(btree, -1, sizeof(btree));
  memset(bfor, -1, sizeof(bfor));
  if (tree(0, le)) {
    printf("YES\n");
    return 0;
  }
  printf("NO\n");
  return 0;
}

```