#include <bits/stdc++.h>
using namespace std;
const int maxn = 24, maxl = 13;
int n, a[maxn + 1], d[maxl + 1][maxn + 1][1 << maxl];
int p = 0;
void reloc() {
  freopen("/Users/admin/Desktop/cards.in", "r", stdin);
  freopen("/Users/admin/Desktop/cards.out", "w", stdout);
  return;
}
void read() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    a[i]--;
  }
  return;
}
void print(int pa) {
  for (int i = 1; i <= n - p; i++)
    if ((1 << (i - 1)) & pa) printf("%d ", i);
  printf("\n");
  return;
}
bool dp(int nd, int leaves, int ch, int pa, int siz) {
  if ((siz == 0 && ch == 1) || nd > n || nd < 0 || leaves < 0 || siz < 0)
    return 0;
  if (siz == 0) {
    if (d[nd][leaves][pa] != -1) return d[nd][leaves][pa];
    if (nd == n - p && leaves == 0 && ch > 1 && pa == (1 << (n - p)) - 1 &&
        siz == 0)
      return d[nd][leaves][pa] = 1;
    return d[nd][leaves][pa] = dp(nd + 1, leaves, 0, pa, a[nd + 1]);
  } else {
    for (int j = 0; j <= leaves && j <= siz; j++) {
      if (j == siz) {
        if (dp(nd, leaves - j, ch + j, pa, 0)) return 1;
      }
      for (int i = nd + 1; a[i] != 0 && i <= n - p; i++) {
        if ((1 << (i - 1) & pa) || (a[i] + 1 > siz - j)) continue;
        if (dp(nd, leaves - j, ch + 1 + j, pa ^ (1 << (i - 1)),
               siz - a[i] - j - 1))
          return 1;
      }
    }
    return 0;
  }
}
bool cmp(int a, int b) { return a > b; }
void work() {
  memset(d, -1, sizeof(d));
  sort(a + 1, a + 1 + n, cmp);
  for (int i = n; i > 0 && a[i] == 0; i--) p++;
  if (p <= n / 2 || (p == n && n != 1)) {
    printf("NO\n");
    return;
  } else if (n == 1 && p == n) {
    printf("YES\n");
    return;
  }
  if (dp(1, p, 0, 1, a[1])) {
    printf("YES\n");
  } else {
    printf("NO\n");
  }
  return;
}
int main() {
  read();
  work();
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 = 24, maxl = 13;
int n, a[maxn + 1], d[maxl + 1][maxn + 1][1 << maxl];
int p = 0;
void reloc() {
  freopen("/Users/admin/Desktop/cards.in", "r", stdin);
  freopen("/Users/admin/Desktop/cards.out", "w", stdout);
  return;
}
void read() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    a[i]--;
  }
  return;
}
void print(int pa) {
  for (int i = 1; i <= n - p; i++)
    if ((1 << (i - 1)) & pa) printf("%d ", i);
  printf("\n");
  return;
}
bool dp(int nd, int leaves, int ch, int pa, int siz) {
  if ((siz == 0 && ch == 1) || nd > n || nd < 0 || leaves < 0 || siz < 0)
    return 0;
  if (siz == 0) {
    if (d[nd][leaves][pa] != -1) return d[nd][leaves][pa];
    if (nd == n - p && leaves == 0 && ch > 1 && pa == (1 << (n - p)) - 1 &&
        siz == 0)
      return d[nd][leaves][pa] = 1;
    return d[nd][leaves][pa] = dp(nd + 1, leaves, 0, pa, a[nd + 1]);
  } else {
    for (int j = 0; j <= leaves && j <= siz; j++) {
      if (j == siz) {
        if (dp(nd, leaves - j, ch + j, pa, 0)) return 1;
      }
      for (int i = nd + 1; a[i] != 0 && i <= n - p; i++) {
        if ((1 << (i - 1) & pa) || (a[i] + 1 > siz - j)) continue;
        if (dp(nd, leaves - j, ch + 1 + j, pa ^ (1 << (i - 1)),
               siz - a[i] - j - 1))
          return 1;
      }
    }
    return 0;
  }
}
bool cmp(int a, int b) { return a > b; }
void work() {
  memset(d, -1, sizeof(d));
  sort(a + 1, a + 1 + n, cmp);
  for (int i = n; i > 0 && a[i] == 0; i--) p++;
  if (p <= n / 2 || (p == n && n != 1)) {
    printf("NO\n");
    return;
  } else if (n == 1 && p == n) {
    printf("YES\n");
    return;
  }
  if (dp(1, p, 0, 1, a[1])) {
    printf("YES\n");
  } else {
    printf("NO\n");
  }
  return;
}
int main() {
  read();
  work();
  return 0;
}

```