#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool getmin(T *a, const T &b) {
  if (b < *a) {
    *a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool getmax(T *a, const T &b) {
  if (b > *a) {
    *a = b;
    return true;
  }
  return false;
}
template <class T>
inline void read(T *a) {
  char c;
  while (isspace(c = getchar())) {
  }
  bool flag = 0;
  if (c == '-')
    flag = 1, *a = 0;
  else
    *a = c - 48;
  while (isdigit(c = getchar())) *a = *a * 10 + c - 48;
  if (flag) *a = -*a;
}
const int mo = 1000000007;
template <class T>
T pow(T a, T b, int c = mo) {
  T res = 1;
  for (T i = 1; i <= b; i <<= 1, a = 1LL * a * a % c)
    if (b & i) res = 1LL * res * a % c;
  return res;
}
const int N = 25;
bool f[1 << 12][N];
int s[1 << 12];
int n, a[N], m, z;
int main() {
  cin >> n;
  for (int i = (1); i <= (n); ++i) {
    int x;
    read(&x);
    if (x > 1)
      a[m++] = x;
    else
      ++z;
  }
  if (2 * z < n) {
    cout << "NO" << endl;
    return 0;
  }
  sort(a, a + m);
  for (int i = (0); i <= ((1 << m) - 1); ++i)
    for (int j = (0); j <= (m - 1); ++j)
      if (i & (1 << j)) s[i] += a[j];
  f[0][z] = 1;
  for (int i = (0); i <= (m - 1); ++i)
    for (int j = (0); j <= ((1 << i) - 1); ++j) {
      for (int k = j;; k = (k - 1) & j)
        if (s[k] < a[i]) {
          if (a[i] - s[k] - 1 + __builtin_popcount(k) > 1)
            for (int p = (a[i] - s[k] - 1); p <= (z); ++p)
              f[(j ^ k) | (1 << i)][p - a[i] + s[k] + 1] |= f[j][p];
          if (k == 0) break;
        }
    }
  if (!m) {
    if (z == 1)
      puts("YES");
    else
      puts("NO");
    return 0;
  }
  if (f[1 << (m - 1)][0])
    puts("YES");
  else
    puts("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;
template <class T>
inline bool getmin(T *a, const T &b) {
  if (b < *a) {
    *a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool getmax(T *a, const T &b) {
  if (b > *a) {
    *a = b;
    return true;
  }
  return false;
}
template <class T>
inline void read(T *a) {
  char c;
  while (isspace(c = getchar())) {
  }
  bool flag = 0;
  if (c == '-')
    flag = 1, *a = 0;
  else
    *a = c - 48;
  while (isdigit(c = getchar())) *a = *a * 10 + c - 48;
  if (flag) *a = -*a;
}
const int mo = 1000000007;
template <class T>
T pow(T a, T b, int c = mo) {
  T res = 1;
  for (T i = 1; i <= b; i <<= 1, a = 1LL * a * a % c)
    if (b & i) res = 1LL * res * a % c;
  return res;
}
const int N = 25;
bool f[1 << 12][N];
int s[1 << 12];
int n, a[N], m, z;
int main() {
  cin >> n;
  for (int i = (1); i <= (n); ++i) {
    int x;
    read(&x);
    if (x > 1)
      a[m++] = x;
    else
      ++z;
  }
  if (2 * z < n) {
    cout << "NO" << endl;
    return 0;
  }
  sort(a, a + m);
  for (int i = (0); i <= ((1 << m) - 1); ++i)
    for (int j = (0); j <= (m - 1); ++j)
      if (i & (1 << j)) s[i] += a[j];
  f[0][z] = 1;
  for (int i = (0); i <= (m - 1); ++i)
    for (int j = (0); j <= ((1 << i) - 1); ++j) {
      for (int k = j;; k = (k - 1) & j)
        if (s[k] < a[i]) {
          if (a[i] - s[k] - 1 + __builtin_popcount(k) > 1)
            for (int p = (a[i] - s[k] - 1); p <= (z); ++p)
              f[(j ^ k) | (1 << i)][p - a[i] + s[k] + 1] |= f[j][p];
          if (k == 0) break;
        }
    }
  if (!m) {
    if (z == 1)
      puts("YES");
    else
      puts("NO");
    return 0;
  }
  if (f[1 << (m - 1)][0])
    puts("YES");
  else
    puts("NO");
  return 0;
}

```