#include <bits/stdc++.h>
using namespace std;
template <class A, class B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
template <class C>
void operator<<(vector<C> &v, const C &x) {
  v.push_back(x);
}
template <class D>
void operator>>(vector<D> &v, D &x) {
  assert(!v.empty());
  x = v.back();
  v.pop_back();
}
template <class E>
void operator<<(set<E> &v, const E &x) {
  v.insert(x);
}
template <class F>
void operator<<(queue<F> &c, const F &v) {
  v.push(v);
}
template <class G>
void operator>>(queue<G> &c, const G &v) {
  const G r = v.front();
  v.pop();
  return r;
}
const int inf = 0x3f3f3f3f;
const long long inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int maxn = 25;
const int maxk = 12;
int n, k;
int c[maxn];
inline int bit(int t) { return 1 << t; }
int bitcnt(int t) { return __builtin_popcount(t); }
int summask[1 << maxk];
int maxmask[1 << maxk];
int dp[1 << maxk][maxn];
int ldp[1 << maxk][maxn];
int go(int mask, int ones) {
  int &res = dp[mask][ones];
  if (res) return res;
  int root = maxmask[mask];
  if ((bitcnt(mask) + ones) != c[root]) {
    res = -1;
    return res;
  }
  if (mask == bit(root)) {
    if (ones >= 2)
      res = 1;
    else
      res = -1;
    return res;
  }
  for (int i = 0; i < mask; ++i)
    if ((i & mask) == i) {
      for (int q = 0; q <= ones; ++q) go(i, q);
    }
  memset(ldp, 0, sizeof(ldp));
  ldp[mask][ones] = true;
  for (int i = mask; i > 0; --i)
    for (int j = ones; j >= 0; --j)
      if (ldp[i][j]) {
        for (int submask = 0; submask <= i; ++submask)
          if ((submask & i) == submask) {
            for (int subj = 0; subj <= j; ++subj) {
              ;
              ;
              ;
              ;
              ;
              if (dp[submask][subj] == 1) {
                ldp[i ^ submask][j - subj] = true;
              }
            }
          }
      }
  res = -1;
  for (int j = 0; j <= ones; ++j)
    if (ldp[bit(root)][j]) res = 1;
  ;
  ;
  ;
  return res;
}
bool take[maxk];
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  int mxid = 0;
  for (int i = 0; i < n; ++i) {
    cin >> c[i];
    if (c[i] > 1) ++k;
    if (c[i] > c[mxid]) mxid = i;
    if (c[i] == 2) {
      cout << "NO" << endl;
      return 0;
    }
  }
  if (c[mxid] != n || k > maxk) {
    cout << "NO" << endl;
    return 0;
  }
  int ones = n - k;
  if (n == 1) {
    cout << (c[0] == 1 ? "YES" : "NO") << endl;
    return 0;
  }
  sort(c, c + n);
  reverse(c, c + n);
  bool ok = false;
  int preones = ones;
  for (int _ = 0; _ < 1000000; ++_) {
    memset(take, 0, sizeof(take));
    take[0] = true;
    ones = preones;
    bool fail = false;
    for (int i = 0; i < k; ++i) {
      take[i] = true;
      int req = c[i] - 1;
      for (int j = 0; j < k; ++j)
        if (!take[j] && c[j] < c[i] - 1 && c[j] <= req) {
          req -= c[j];
          take[j] = true;
        }
      if (req > ones) {
        fail = true;
        break;
      }
      ones -= req;
    }
    for (int j = 0; j < k; ++j)
      if (!take[j]) fail = true;
    if (ones) fail = true;
    if (!fail) {
      ok = true;
      break;
    }
    random_shuffle(c + 1, c + k);
  }
  if (ok)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

### 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;
template <class A, class B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
template <class C>
void operator<<(vector<C> &v, const C &x) {
  v.push_back(x);
}
template <class D>
void operator>>(vector<D> &v, D &x) {
  assert(!v.empty());
  x = v.back();
  v.pop_back();
}
template <class E>
void operator<<(set<E> &v, const E &x) {
  v.insert(x);
}
template <class F>
void operator<<(queue<F> &c, const F &v) {
  v.push(v);
}
template <class G>
void operator>>(queue<G> &c, const G &v) {
  const G r = v.front();
  v.pop();
  return r;
}
const int inf = 0x3f3f3f3f;
const long long inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int maxn = 25;
const int maxk = 12;
int n, k;
int c[maxn];
inline int bit(int t) { return 1 << t; }
int bitcnt(int t) { return __builtin_popcount(t); }
int summask[1 << maxk];
int maxmask[1 << maxk];
int dp[1 << maxk][maxn];
int ldp[1 << maxk][maxn];
int go(int mask, int ones) {
  int &res = dp[mask][ones];
  if (res) return res;
  int root = maxmask[mask];
  if ((bitcnt(mask) + ones) != c[root]) {
    res = -1;
    return res;
  }
  if (mask == bit(root)) {
    if (ones >= 2)
      res = 1;
    else
      res = -1;
    return res;
  }
  for (int i = 0; i < mask; ++i)
    if ((i & mask) == i) {
      for (int q = 0; q <= ones; ++q) go(i, q);
    }
  memset(ldp, 0, sizeof(ldp));
  ldp[mask][ones] = true;
  for (int i = mask; i > 0; --i)
    for (int j = ones; j >= 0; --j)
      if (ldp[i][j]) {
        for (int submask = 0; submask <= i; ++submask)
          if ((submask & i) == submask) {
            for (int subj = 0; subj <= j; ++subj) {
              ;
              ;
              ;
              ;
              ;
              if (dp[submask][subj] == 1) {
                ldp[i ^ submask][j - subj] = true;
              }
            }
          }
      }
  res = -1;
  for (int j = 0; j <= ones; ++j)
    if (ldp[bit(root)][j]) res = 1;
  ;
  ;
  ;
  return res;
}
bool take[maxk];
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  int mxid = 0;
  for (int i = 0; i < n; ++i) {
    cin >> c[i];
    if (c[i] > 1) ++k;
    if (c[i] > c[mxid]) mxid = i;
    if (c[i] == 2) {
      cout << "NO" << endl;
      return 0;
    }
  }
  if (c[mxid] != n || k > maxk) {
    cout << "NO" << endl;
    return 0;
  }
  int ones = n - k;
  if (n == 1) {
    cout << (c[0] == 1 ? "YES" : "NO") << endl;
    return 0;
  }
  sort(c, c + n);
  reverse(c, c + n);
  bool ok = false;
  int preones = ones;
  for (int _ = 0; _ < 1000000; ++_) {
    memset(take, 0, sizeof(take));
    take[0] = true;
    ones = preones;
    bool fail = false;
    for (int i = 0; i < k; ++i) {
      take[i] = true;
      int req = c[i] - 1;
      for (int j = 0; j < k; ++j)
        if (!take[j] && c[j] < c[i] - 1 && c[j] <= req) {
          req -= c[j];
          take[j] = true;
        }
      if (req > ones) {
        fail = true;
        break;
      }
      ones -= req;
    }
    for (int j = 0; j < k; ++j)
      if (!take[j]) fail = true;
    if (ones) fail = true;
    if (!fail) {
      ok = true;
      break;
    }
    random_shuffle(c + 1, c + k);
  }
  if (ok)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

```