#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5, inf = 1e9 + 7;
int n, k, i;
int dp[15][1 << 15][25];
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int i, j, first, second, l = 0, f, g, a, b;
  cin >> n;
  vector<int> v;
  for (i = 0; i < n; i++) {
    cin >> first;
    if (first - 1)
      v.emplace_back(first - 1);
    else
      l++;
  }
  if ((int)v.size() == 0 && n == 1) return cout << "YES", 0;
  if (l <= n / 2 || *min_element(v.begin(), v.end()) == 1) {
    cout << "NO";
    return 0;
  }
  sort(v.begin(), v.end(), greater<int>());
  n = (int)v.size();
  dp[0][(1 << n) - 2][l] = 1;
  for (i = 0; i < (int)v.size(); i++) {
    for (j = 0; j < 1 << (int)v.size(); j++)
      for (k = 0; k < l + 1; k++)
        if (dp[i][j][k]) {
          for (f = j; f > 0; f = (f - 1) & j) {
            a = 0;
            b = 0;
            for (g = i + 1; g < n; g++)
              if (f & (1 << g)) a += v[g] + 1, b++;
            if (b + v[i] - a < 2) continue;
            if (a <= v[i] && a + k >= v[i]) {
              dp[i + 1][j ^ f][k - (v[i] - a)] = 1;
            }
          }
          if (v[i] <= k) dp[i + 1][j][k - v[i]] = 1;
        }
  }
  if (dp[n][0][0] == 1)
    cout << "YES\n";
  else
    cout << "NO\n";
}

### 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 N = 2e3 + 5, inf = 1e9 + 7;
int n, k, i;
int dp[15][1 << 15][25];
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int i, j, first, second, l = 0, f, g, a, b;
  cin >> n;
  vector<int> v;
  for (i = 0; i < n; i++) {
    cin >> first;
    if (first - 1)
      v.emplace_back(first - 1);
    else
      l++;
  }
  if ((int)v.size() == 0 && n == 1) return cout << "YES", 0;
  if (l <= n / 2 || *min_element(v.begin(), v.end()) == 1) {
    cout << "NO";
    return 0;
  }
  sort(v.begin(), v.end(), greater<int>());
  n = (int)v.size();
  dp[0][(1 << n) - 2][l] = 1;
  for (i = 0; i < (int)v.size(); i++) {
    for (j = 0; j < 1 << (int)v.size(); j++)
      for (k = 0; k < l + 1; k++)
        if (dp[i][j][k]) {
          for (f = j; f > 0; f = (f - 1) & j) {
            a = 0;
            b = 0;
            for (g = i + 1; g < n; g++)
              if (f & (1 << g)) a += v[g] + 1, b++;
            if (b + v[i] - a < 2) continue;
            if (a <= v[i] && a + k >= v[i]) {
              dp[i + 1][j ^ f][k - (v[i] - a)] = 1;
            }
          }
          if (v[i] <= k) dp[i + 1][j][k - v[i]] = 1;
        }
  }
  if (dp[n][0][0] == 1)
    cout << "YES\n";
  else
    cout << "NO\n";
}

```