#include <bits/stdc++.h>
using namespace std;
int n, N, cnt, sum[1 << 12];
bool dp[1 << 12][24];
vector<int> vc;
inline int biname(int mask) {
  int ret = 0;
  for (; mask; mask /= 2) ret++;
  return ret;
}
inline int count(int x) {
  int ret = 0;
  for (int i = 0; i < 24; i++)
    if (x & (1 << i)) ret++;
  return ret;
}
int main() {
  cin >> n;
  for (int x, i = 0; i < n; i++) {
    cin >> x;
    if (x == 1)
      cnt++;
    else if (x == 2) {
      cout << "NO" << endl;
      exit(0);
    } else
      vc.push_back(x);
  }
  sort(vc.begin(), vc.end());
  if (n == 1) {
    cout << (cnt == 1 ? "YES" : "NO") << endl;
    exit(0);
  }
  if (cnt < vc.size() || vc.size() == 0 || vc.back() != n) {
    cout << "NO" << endl;
    exit(0);
  }
  for (int i = 0; i < (1 << vc.size()); i++)
    for (int j = 0; j < vc.size(); j++)
      if (i & (1 << j)) sum[i] += vc[j];
  N = vc.size();
  dp[0][cnt] = 1;
  for (int mask = 0; mask < (1 << vc.size()); mask++)
    for (int j = 0; j <= cnt; j++) {
      int hlp = biname(mask);
      if (hlp == vc.size()) continue;
      if (dp[mask][j])
        for (int k = 0; k < (1 << vc.size()); k++)
          if ((mask & k) == k && sum[k] <= (vc[hlp] - 1) &&
              sum[k] + j >= (vc[hlp] - 1)) {
            int next = mask ^ k, need = vc[hlp] - sum[k] - 1;
            next |= (1 << hlp);
            if (need || count(k) > 1) dp[next][j - need] = 1;
          }
    }
  cout << (dp[(1 << (N - 1))][0] ? "YES" : "NO") << endl;
}

### Prompt

Please formulate 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 n, N, cnt, sum[1 << 12];
bool dp[1 << 12][24];
vector<int> vc;
inline int biname(int mask) {
  int ret = 0;
  for (; mask; mask /= 2) ret++;
  return ret;
}
inline int count(int x) {
  int ret = 0;
  for (int i = 0; i < 24; i++)
    if (x & (1 << i)) ret++;
  return ret;
}
int main() {
  cin >> n;
  for (int x, i = 0; i < n; i++) {
    cin >> x;
    if (x == 1)
      cnt++;
    else if (x == 2) {
      cout << "NO" << endl;
      exit(0);
    } else
      vc.push_back(x);
  }
  sort(vc.begin(), vc.end());
  if (n == 1) {
    cout << (cnt == 1 ? "YES" : "NO") << endl;
    exit(0);
  }
  if (cnt < vc.size() || vc.size() == 0 || vc.back() != n) {
    cout << "NO" << endl;
    exit(0);
  }
  for (int i = 0; i < (1 << vc.size()); i++)
    for (int j = 0; j < vc.size(); j++)
      if (i & (1 << j)) sum[i] += vc[j];
  N = vc.size();
  dp[0][cnt] = 1;
  for (int mask = 0; mask < (1 << vc.size()); mask++)
    for (int j = 0; j <= cnt; j++) {
      int hlp = biname(mask);
      if (hlp == vc.size()) continue;
      if (dp[mask][j])
        for (int k = 0; k < (1 << vc.size()); k++)
          if ((mask & k) == k && sum[k] <= (vc[hlp] - 1) &&
              sum[k] + j >= (vc[hlp] - 1)) {
            int next = mask ^ k, need = vc[hlp] - sum[k] - 1;
            next |= (1 << hlp);
            if (need || count(k) > 1) dp[next][j - need] = 1;
          }
    }
  cout << (dp[(1 << (N - 1))][0] ? "YES" : "NO") << endl;
}

```