#include <bits/stdc++.h>
using namespace std;
bool check(long long n, long long pos) { return n & (1LL << pos); }
long long Set(long long n, long long pos) { return n = n | (1LL << pos); }
vector<long long> vec;
long long dp[13][(1 << 13)][25];
long long solve(long long pos, long long mask, long long leaf) {
  long long &ret = dp[pos][mask][leaf];
  if (ret != -1) return ret;
  if (pos == vec.size()) {
    if (!(mask || leaf)) return ret = 1;
    return ret = 0;
  }
  if (check(mask, pos)) return ret = 0;
  ret = 0;
  if (vec[pos] - 1 <= leaf && vec[pos] - 1 >= 2) {
    ret |= solve(pos + 1, mask, leaf - vec[pos] + 1);
  }
  if (ret == 1) return ret;
  for (long long submask = mask; submask; submask = (submask - 1) & mask) {
    long long totnode = 0, subtree = 0;
    for (long long i = pos + 1; i < vec.size(); i++) {
      if (check(submask, i)) {
        totnode++;
        subtree += vec[i];
      }
    }
    long long forleaf = vec[pos] - subtree - 1;
    if (forleaf > leaf) continue;
    if (totnode + forleaf <= 1) continue;
    ret |= solve(pos + 1, mask ^ submask, leaf - forleaf);
    if (ret == 1) return ret;
  }
  return ret;
}
int main() {
  long long i, j, k, l, m, n, o, r, q;
  long long testcase;
  long long input, flag, tag, ans;
  while (cin >> n) {
    vec.clear();
    memset(dp, -1, sizeof dp);
    long long leaf = 0;
    for (long long i = 1; i <= n; i++) {
      scanf("%lld", &input);
      if (input == 1)
        leaf++;
      else
        vec.push_back(input);
    }
    sort(vec.rbegin(), vec.rend());
    if (leaf < (n + 1) / 2) {
      printf("NO\n");
      continue;
    }
    if (n == 1) {
      if (leaf == 1)
        printf("YES\n");
      else
        printf("NO\n");
      continue;
    }
    ans = solve(0, ((1 << vec.size()) - 1) ^ 1, leaf);
    if (ans == 1)
      printf("YES\n");
    else
      printf("NO\n");
  }
}

### Prompt

Please create a solution in CPP 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;
bool check(long long n, long long pos) { return n & (1LL << pos); }
long long Set(long long n, long long pos) { return n = n | (1LL << pos); }
vector<long long> vec;
long long dp[13][(1 << 13)][25];
long long solve(long long pos, long long mask, long long leaf) {
  long long &ret = dp[pos][mask][leaf];
  if (ret != -1) return ret;
  if (pos == vec.size()) {
    if (!(mask || leaf)) return ret = 1;
    return ret = 0;
  }
  if (check(mask, pos)) return ret = 0;
  ret = 0;
  if (vec[pos] - 1 <= leaf && vec[pos] - 1 >= 2) {
    ret |= solve(pos + 1, mask, leaf - vec[pos] + 1);
  }
  if (ret == 1) return ret;
  for (long long submask = mask; submask; submask = (submask - 1) & mask) {
    long long totnode = 0, subtree = 0;
    for (long long i = pos + 1; i < vec.size(); i++) {
      if (check(submask, i)) {
        totnode++;
        subtree += vec[i];
      }
    }
    long long forleaf = vec[pos] - subtree - 1;
    if (forleaf > leaf) continue;
    if (totnode + forleaf <= 1) continue;
    ret |= solve(pos + 1, mask ^ submask, leaf - forleaf);
    if (ret == 1) return ret;
  }
  return ret;
}
int main() {
  long long i, j, k, l, m, n, o, r, q;
  long long testcase;
  long long input, flag, tag, ans;
  while (cin >> n) {
    vec.clear();
    memset(dp, -1, sizeof dp);
    long long leaf = 0;
    for (long long i = 1; i <= n; i++) {
      scanf("%lld", &input);
      if (input == 1)
        leaf++;
      else
        vec.push_back(input);
    }
    sort(vec.rbegin(), vec.rend());
    if (leaf < (n + 1) / 2) {
      printf("NO\n");
      continue;
    }
    if (n == 1) {
      if (leaf == 1)
        printf("YES\n");
      else
        printf("NO\n");
      continue;
    }
    ans = solve(0, ((1 << vec.size()) - 1) ^ 1, leaf);
    if (ans == 1)
      printf("YES\n");
    else
      printf("NO\n");
  }
}

```