#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647;
const long long LLINF = 9223372036854775807LL;
const int ST = 100010;
const int ST1 = 1000010;
const long long MOD = 1000000007;
long long ABS(long long a) {
  if (a < 0)
    return a * (-1);
  else
    return a;
}
int mas[30];
bool ans = true;
void bad() {
  cout << "NO";
  exit(0);
}
vector<vector<int> > ppp;
int sz = 0;
void per(vector<int> &t) {
  if ((int)((t).size()) == sz) {
    ppp.push_back(t);
  } else {
    t.push_back(0);
    per(t);
    t.pop_back();
    t.push_back(1);
    per(t);
    t.pop_back();
  }
}
void per(vector<int> val, int ed, vector<int> zap) {
  if ((int)((val).size()) == 0) {
    if (ed == 0) {
      cout << "YES";
      exit(0);
    } else
      return;
  }
  vector<vector<int> > pp;
  vector<int> em;
  sz = (int)((zap).size());
  ppp.clear();
  per(em);
  pp = ppp;
  int tek = val[(int)((val).size()) - 1] - 1;
  val.pop_back();
  int ost = 0;
  for (int i = 0; i < (int)((pp).size()); i++) {
    vector<int> next;
    next.push_back(tek + 1);
    ost = 0;
    int kk = 0;
    for (int j = 0; j < (int)((pp[i]).size()); j++) {
      if (pp[i][j] == 1) {
        ost += zap[j];
        kk++;
      } else
        next.push_back(zap[j]);
    }
    if (ost <= tek) {
      int s = tek - ost;
      if (s > ed) continue;
      kk += s;
      if (kk == 1) continue;
      per(val, ed - s, next);
    }
  }
}
int main() {
  int n;
  cin >> n;
  if (n == 1) {
    cout << "YES";
    return 0;
  }
  int kk = 0;
  for (int i = 0; i < n; i++) {
    cin >> mas[i];
    if (mas[i] == 2) bad();
    if (mas[i] == 1) kk++;
  }
  sort(mas, mas + n);
  int mn = n / 2;
  if (kk < mn) bad();
  vector<int> t;
  int nol = 0;
  for (int i = 0; i < n; i++)
    if (mas[i] != 1)
      t.push_back(mas[i]);
    else
      nol++;
  vector<int> em;
  reverse(t.begin(), t.end());
  per(t, nol, em);
  cout << "NO";
  return 0;
}

### 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;
const int INF = 2147483647;
const long long LLINF = 9223372036854775807LL;
const int ST = 100010;
const int ST1 = 1000010;
const long long MOD = 1000000007;
long long ABS(long long a) {
  if (a < 0)
    return a * (-1);
  else
    return a;
}
int mas[30];
bool ans = true;
void bad() {
  cout << "NO";
  exit(0);
}
vector<vector<int> > ppp;
int sz = 0;
void per(vector<int> &t) {
  if ((int)((t).size()) == sz) {
    ppp.push_back(t);
  } else {
    t.push_back(0);
    per(t);
    t.pop_back();
    t.push_back(1);
    per(t);
    t.pop_back();
  }
}
void per(vector<int> val, int ed, vector<int> zap) {
  if ((int)((val).size()) == 0) {
    if (ed == 0) {
      cout << "YES";
      exit(0);
    } else
      return;
  }
  vector<vector<int> > pp;
  vector<int> em;
  sz = (int)((zap).size());
  ppp.clear();
  per(em);
  pp = ppp;
  int tek = val[(int)((val).size()) - 1] - 1;
  val.pop_back();
  int ost = 0;
  for (int i = 0; i < (int)((pp).size()); i++) {
    vector<int> next;
    next.push_back(tek + 1);
    ost = 0;
    int kk = 0;
    for (int j = 0; j < (int)((pp[i]).size()); j++) {
      if (pp[i][j] == 1) {
        ost += zap[j];
        kk++;
      } else
        next.push_back(zap[j]);
    }
    if (ost <= tek) {
      int s = tek - ost;
      if (s > ed) continue;
      kk += s;
      if (kk == 1) continue;
      per(val, ed - s, next);
    }
  }
}
int main() {
  int n;
  cin >> n;
  if (n == 1) {
    cout << "YES";
    return 0;
  }
  int kk = 0;
  for (int i = 0; i < n; i++) {
    cin >> mas[i];
    if (mas[i] == 2) bad();
    if (mas[i] == 1) kk++;
  }
  sort(mas, mas + n);
  int mn = n / 2;
  if (kk < mn) bad();
  vector<int> t;
  int nol = 0;
  for (int i = 0; i < n; i++)
    if (mas[i] != 1)
      t.push_back(mas[i]);
    else
      nol++;
  vector<int> em;
  reverse(t.begin(), t.end());
  per(t, nol, em);
  cout << "NO";
  return 0;
}

```