#include <bits/stdc++.h>
using namespace std;
int pd[12][25][4096];
bool search(int x, int N, vector<int>& V, int nr_1, int mask) {
  if (pd[x][nr_1][mask]) {
    return pd[x][nr_1][mask] == 1;
  }
  if (x == V.size() - 1) {
    return V[x] == N;
  }
  int val = V[x] - 1;
  int ok = false;
  for (int i = 0; !ok && i <= nr_1; i++) {
    int my_val = val - i;
    if (my_val == 0) {
      if (i > 1) {
        ok = search(x + 1, N, V, nr_1 - i, mask);
        if (ok) continue;
      }
    }
    if (x > 0) {
      for (int j = 0; !ok && j < (1 << x); j++) {
        bool good = true;
        int nr_good = i;
        int rem = my_val;
        for (int k = 0; good && k < x; k++)
          if (j & (1 << k)) {
            nr_good++;
            if (mask & (1 << k)) good = false;
            rem -= V[k];
          }
        if (!good || nr_good < 2 || rem != 0) continue;
        ok = search(x + 1, N, V, nr_1 - i, mask | j);
      }
    }
  }
  pd[x][nr_1][mask] = ok ? 1 : 2;
  return ok;
}
int main() {
  int N;
  scanf("%d", &N);
  vector<int> V;
  int nr_1 = 0;
  for (int i = 0; i < N; i++) {
    int x;
    scanf("%d", &x);
    if (x == 1)
      nr_1++;
    else
      V.push_back(x);
  }
  sort(V.begin(), V.end());
  int min_nr_1 = (N + 1) / 2;
  if (N == 1) {
    printf("%s\n", nr_1 == 1 ? "YES" : "NO");
    return 0;
  }
  if (N == 2) {
    printf("NO\n");
    return 0;
  }
  if (nr_1 < min_nr_1 || V.size() == 0 || V[V.size() - 1] != N) {
    printf("NO\n");
    return 0;
  }
  bool ok = search(0, N, V, nr_1, 0);
  printf("%s\n", ok ? "YES" : "NO");
  return 0;
}

### Prompt

Your task is to create 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;
int pd[12][25][4096];
bool search(int x, int N, vector<int>& V, int nr_1, int mask) {
  if (pd[x][nr_1][mask]) {
    return pd[x][nr_1][mask] == 1;
  }
  if (x == V.size() - 1) {
    return V[x] == N;
  }
  int val = V[x] - 1;
  int ok = false;
  for (int i = 0; !ok && i <= nr_1; i++) {
    int my_val = val - i;
    if (my_val == 0) {
      if (i > 1) {
        ok = search(x + 1, N, V, nr_1 - i, mask);
        if (ok) continue;
      }
    }
    if (x > 0) {
      for (int j = 0; !ok && j < (1 << x); j++) {
        bool good = true;
        int nr_good = i;
        int rem = my_val;
        for (int k = 0; good && k < x; k++)
          if (j & (1 << k)) {
            nr_good++;
            if (mask & (1 << k)) good = false;
            rem -= V[k];
          }
        if (!good || nr_good < 2 || rem != 0) continue;
        ok = search(x + 1, N, V, nr_1 - i, mask | j);
      }
    }
  }
  pd[x][nr_1][mask] = ok ? 1 : 2;
  return ok;
}
int main() {
  int N;
  scanf("%d", &N);
  vector<int> V;
  int nr_1 = 0;
  for (int i = 0; i < N; i++) {
    int x;
    scanf("%d", &x);
    if (x == 1)
      nr_1++;
    else
      V.push_back(x);
  }
  sort(V.begin(), V.end());
  int min_nr_1 = (N + 1) / 2;
  if (N == 1) {
    printf("%s\n", nr_1 == 1 ? "YES" : "NO");
    return 0;
  }
  if (N == 2) {
    printf("NO\n");
    return 0;
  }
  if (nr_1 < min_nr_1 || V.size() == 0 || V[V.size() - 1] != N) {
    printf("NO\n");
    return 0;
  }
  bool ok = search(0, N, V, nr_1, 0);
  printf("%s\n", ok ? "YES" : "NO");
  return 0;
}

```