#include <bits/stdc++.h>
using namespace std;
int n, leaff, w[28], vis[28][28][(1 << (28 / 2))];
bool dp[28][28][(1 << (28 / 2))];
vector<int> v;
void f(int now, int cur, int mask, int chlds, int leafs, int node,
       vector<pair<pair<int, int>, int> > &sts) {
  if (cur > w[node] - 1) return;
  if (leafs >= w[node] - cur - 1 && chlds + w[node] - cur - 1 >= 2) {
    sts.push_back(
        make_pair(make_pair(node + 1, mask), leafs - w[node] + cur + 1));
  }
  if (now == (int)v.size()) return;
  f(now + 1, cur + w[v[now]], mask | (1 << (v[now] - 1)), chlds + 1, leafs,
    node, sts);
  f(now + 1, cur, mask, chlds, leafs, node, sts);
}
void cstates(vector<pair<pair<int, int>, int> > &sts, int node, int mask,
             int leafs) {
  v.clear();
  for (int i = 0; i < n - leaff; i++) {
    if (mask & (1 << i)) continue;
    v.push_back(i + 1);
  }
  f(0, 0, 0, 0, leafs, node, sts);
}
bool dfs(int node, int mask, int leafs) {
  vector<pair<pair<int, int>, int> > sts;
  bool ret = false;
  if (node == n - leaff + 1) {
    if (leafs == 0) return true;
    return false;
  }
  if (vis[node][leafs][mask]) return dp[node][leafs][mask];
  if (!(mask & (1 << (node - 1)))) return false;
  cstates(sts, node, mask, leafs);
  for (pair<pair<int, int>, int> i : sts) {
    ret |= dfs(i.first.first, mask | i.first.second, i.second);
  }
  vis[node][leafs][mask] = 1;
  return dp[node][leafs][mask] = ret;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &w[i]);
    leaff += (w[i] == 1);
  }
  if (n == 1 && leaff == 1) {
    printf("YES");
    return 0;
  }
  if (leaff < (n + 1) / 2) {
    printf("NO");
    return 0;
  }
  sort(w + 1, w + 1 + n, greater<int>());
  bool ans = dfs(1, 1, leaff);
  if (ans)
    printf("YES");
  else
    printf("NO");
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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, leaff, w[28], vis[28][28][(1 << (28 / 2))];
bool dp[28][28][(1 << (28 / 2))];
vector<int> v;
void f(int now, int cur, int mask, int chlds, int leafs, int node,
       vector<pair<pair<int, int>, int> > &sts) {
  if (cur > w[node] - 1) return;
  if (leafs >= w[node] - cur - 1 && chlds + w[node] - cur - 1 >= 2) {
    sts.push_back(
        make_pair(make_pair(node + 1, mask), leafs - w[node] + cur + 1));
  }
  if (now == (int)v.size()) return;
  f(now + 1, cur + w[v[now]], mask | (1 << (v[now] - 1)), chlds + 1, leafs,
    node, sts);
  f(now + 1, cur, mask, chlds, leafs, node, sts);
}
void cstates(vector<pair<pair<int, int>, int> > &sts, int node, int mask,
             int leafs) {
  v.clear();
  for (int i = 0; i < n - leaff; i++) {
    if (mask & (1 << i)) continue;
    v.push_back(i + 1);
  }
  f(0, 0, 0, 0, leafs, node, sts);
}
bool dfs(int node, int mask, int leafs) {
  vector<pair<pair<int, int>, int> > sts;
  bool ret = false;
  if (node == n - leaff + 1) {
    if (leafs == 0) return true;
    return false;
  }
  if (vis[node][leafs][mask]) return dp[node][leafs][mask];
  if (!(mask & (1 << (node - 1)))) return false;
  cstates(sts, node, mask, leafs);
  for (pair<pair<int, int>, int> i : sts) {
    ret |= dfs(i.first.first, mask | i.first.second, i.second);
  }
  vis[node][leafs][mask] = 1;
  return dp[node][leafs][mask] = ret;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &w[i]);
    leaff += (w[i] == 1);
  }
  if (n == 1 && leaff == 1) {
    printf("YES");
    return 0;
  }
  if (leaff < (n + 1) / 2) {
    printf("NO");
    return 0;
  }
  sort(w + 1, w + 1 + n, greater<int>());
  bool ans = dfs(1, 1, leaff);
  if (ans)
    printf("YES");
  else
    printf("NO");
}

```