#include <bits/stdc++.h>
using ll = int;
const ll mod = 1e15 + 7;
const ll N = 1005;
const int base = 400;
using ull = unsigned long long;
using namespace std;
ll n, m, t, k, T, a[N], dp[N], lab[N], u, v, b[N], d[N], tong, cnt, q, c[N];
ll ans;
vector<ll> adj[N];
vector<pair<ll, ll> > kq;
void hop(ll u, ll v) {
  lab[u] += lab[v];
  lab[v] = u;
}
ll findp(ll u) { return lab[u] < 0 ? u : lab[u] = findp(lab[u]); }
pair<ll, ll> p[N];
ll dis(pair<ll, ll> x, pair<ll, ll> y) {
  return (x.first - y.first) * (x.first - y.first) +
         (x.second - y.second) * (x.second - y.second);
}
ll getmn(ll l, ll r) {
  ll total = mod;
  for (int i = l; i < r; i++) {
    for (int j = i + 1; j <= r; j++) total = min(total, dis(p[i], p[j]));
  }
  ans = min(ans, total);
  return total;
}
void findmn(vector<pair<ll, ll> > pi) {
  sort(pi.begin(), pi.end());
  for (int i = 0; i < pi.size(); i++) {
    for (int j = i + 1; j < pi.size(); j++) {
      if ((p[i].first - p[j].first) * (pi[i].first - pi[j].first) > ans) break;
      ans = min(ans, dis(pi[i], pi[j]));
    }
  }
}
ll cal(ll l, ll r) {
  if (r - l <= 3) return getmn(l, r);
  ll mid = (l + r) / 2;
  ll total = min(cal(l, mid), cal(mid, r));
  kq.clear();
  for (int i = l; i <= r; i++) {
    if ((p[i].first - p[mid].first) * (p[i].first - p[mid].first) <= ans)
      kq.push_back({p[i].second, p[i].first});
  }
  findmn(kq);
  total = min(total, ans);
  return total;
}
void backtrack(ll i) {
  if (a[i] == 1) {
    bool ok = true;
    ll total = 0;
    for (int j = i + 1; j <= n; j++) {
      if (a[j] - 1 - d[j] + b[j] < 2) ok = false;
      total += a[j] - 1 - d[j];
    }
    if (ok && total == i) {
      cout << "YES";
      exit(0);
    }
    return;
  }
  if (i == 1) return;
  for (int j = i + 1; j <= n; j++) {
    if (a[j] - 1 >= d[j] + a[i]) {
      d[j] += a[i];
      ++b[j];
      backtrack(i - 1);
      d[j] -= a[i];
      --b[j];
    }
  }
}
void sol() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (tong == a[i]) ++tong;
    tong = max(a[i], tong);
    if (a[i] == 2) ans = 1;
  }
  if (n == 1) {
    if (a[1] == 1) {
      cout << "YES";
    } else
      cout << "NO";
    return;
  }
  sort(a + 1, a + 1 + n);
  if (ans == 1 || tong != n || a[1] != 1) {
    cout << "NO";
    return;
  }
  backtrack(n - 1);
  cout << "NO";
}
int main() {
  if (fopen("pieaters"
            ".inp",
            "r")) {
    freopen(
        "pieaters"
        ".inp",
        "r", stdin);
    freopen(
        "pieaters"
        ".out",
        "w", stdout);
  }
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int ntest;
  ntest = 1;
  while (ntest-- > 0) sol();
}

### 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 ll = int;
const ll mod = 1e15 + 7;
const ll N = 1005;
const int base = 400;
using ull = unsigned long long;
using namespace std;
ll n, m, t, k, T, a[N], dp[N], lab[N], u, v, b[N], d[N], tong, cnt, q, c[N];
ll ans;
vector<ll> adj[N];
vector<pair<ll, ll> > kq;
void hop(ll u, ll v) {
  lab[u] += lab[v];
  lab[v] = u;
}
ll findp(ll u) { return lab[u] < 0 ? u : lab[u] = findp(lab[u]); }
pair<ll, ll> p[N];
ll dis(pair<ll, ll> x, pair<ll, ll> y) {
  return (x.first - y.first) * (x.first - y.first) +
         (x.second - y.second) * (x.second - y.second);
}
ll getmn(ll l, ll r) {
  ll total = mod;
  for (int i = l; i < r; i++) {
    for (int j = i + 1; j <= r; j++) total = min(total, dis(p[i], p[j]));
  }
  ans = min(ans, total);
  return total;
}
void findmn(vector<pair<ll, ll> > pi) {
  sort(pi.begin(), pi.end());
  for (int i = 0; i < pi.size(); i++) {
    for (int j = i + 1; j < pi.size(); j++) {
      if ((p[i].first - p[j].first) * (pi[i].first - pi[j].first) > ans) break;
      ans = min(ans, dis(pi[i], pi[j]));
    }
  }
}
ll cal(ll l, ll r) {
  if (r - l <= 3) return getmn(l, r);
  ll mid = (l + r) / 2;
  ll total = min(cal(l, mid), cal(mid, r));
  kq.clear();
  for (int i = l; i <= r; i++) {
    if ((p[i].first - p[mid].first) * (p[i].first - p[mid].first) <= ans)
      kq.push_back({p[i].second, p[i].first});
  }
  findmn(kq);
  total = min(total, ans);
  return total;
}
void backtrack(ll i) {
  if (a[i] == 1) {
    bool ok = true;
    ll total = 0;
    for (int j = i + 1; j <= n; j++) {
      if (a[j] - 1 - d[j] + b[j] < 2) ok = false;
      total += a[j] - 1 - d[j];
    }
    if (ok && total == i) {
      cout << "YES";
      exit(0);
    }
    return;
  }
  if (i == 1) return;
  for (int j = i + 1; j <= n; j++) {
    if (a[j] - 1 >= d[j] + a[i]) {
      d[j] += a[i];
      ++b[j];
      backtrack(i - 1);
      d[j] -= a[i];
      --b[j];
    }
  }
}
void sol() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (tong == a[i]) ++tong;
    tong = max(a[i], tong);
    if (a[i] == 2) ans = 1;
  }
  if (n == 1) {
    if (a[1] == 1) {
      cout << "YES";
    } else
      cout << "NO";
    return;
  }
  sort(a + 1, a + 1 + n);
  if (ans == 1 || tong != n || a[1] != 1) {
    cout << "NO";
    return;
  }
  backtrack(n - 1);
  cout << "NO";
}
int main() {
  if (fopen("pieaters"
            ".inp",
            "r")) {
    freopen(
        "pieaters"
        ".inp",
        "r", stdin);
    freopen(
        "pieaters"
        ".out",
        "w", stdout);
  }
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int ntest;
  ntest = 1;
  while (ntest-- > 0) sol();
}

```