#include <bits/stdc++.h>
using namespace std;
const int maxn = 30;
const int maxk = 120;
const int logn = 18;
const int MOd = 1e9 + 7;
int a, ar[maxn], dn[maxn][(1 << 12) + 20], s1;
vector<int> w;
int main() {
  scanf("%d", &a);
  for (int i = 1; i <= a; i++) scanf("%d", &ar[i]);
  sort(ar + 1, ar + 1 + a);
  s1 = 1;
  while (s1 <= a && ar[s1] == 1) s1++;
  s1--;
  if (s1 <= a / 2) {
    printf("NO\n");
    return 0;
  }
  int b = 0, bs[maxn];
  for (int i = s1 + 1; i <= a; i++) bs[++b] = ar[i];
  if (b == 0) {
    if (a == 1)
      printf("YES\n");
    else
      printf("NO\n");
    return 0;
  }
  a = b;
  for (int i = 1; i <= a; i++) ar[i - 1] = bs[i];
  a--;
  dn[0][1 << (a)] = 1;
  for (int i = 0; i <= s1; i++)
    for (int j = (1 << a) - 1; j >= 0; j--) {
      w.clear();
      int s = -1, beg = 0;
      for (int k = 0; k < a; k++)
        if ((1 << k) & j) w.push_back(k), s = k, beg |= 1 << k;
      s++;
      beg |= 1 << s;
      for (int k = (1 << w.size()) - 1; k >= 0; k--) {
        int t = 0, t2 = beg, cnt = 0;
        for (int l = 0; l < w.size(); l++)
          if ((1 << l) & k) t += ar[w[l]], t2 ^= (1 << w[l]), cnt++;
        if (ar[s] - 1 - t <= i) {
          if ((ar[s] - 1 - t) + cnt <= 1) continue;
          dn[i][j] |= dn[i - (ar[s] - 1 - t)][t2];
        }
        if (dn[i][j]) break;
      }
    }
  if (dn[s1][0])
    printf("YES\n");
  else
    printf("NO\n");
  return 0;
}

### Prompt

In CPP, your task is to solve 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 maxn = 30;
const int maxk = 120;
const int logn = 18;
const int MOd = 1e9 + 7;
int a, ar[maxn], dn[maxn][(1 << 12) + 20], s1;
vector<int> w;
int main() {
  scanf("%d", &a);
  for (int i = 1; i <= a; i++) scanf("%d", &ar[i]);
  sort(ar + 1, ar + 1 + a);
  s1 = 1;
  while (s1 <= a && ar[s1] == 1) s1++;
  s1--;
  if (s1 <= a / 2) {
    printf("NO\n");
    return 0;
  }
  int b = 0, bs[maxn];
  for (int i = s1 + 1; i <= a; i++) bs[++b] = ar[i];
  if (b == 0) {
    if (a == 1)
      printf("YES\n");
    else
      printf("NO\n");
    return 0;
  }
  a = b;
  for (int i = 1; i <= a; i++) ar[i - 1] = bs[i];
  a--;
  dn[0][1 << (a)] = 1;
  for (int i = 0; i <= s1; i++)
    for (int j = (1 << a) - 1; j >= 0; j--) {
      w.clear();
      int s = -1, beg = 0;
      for (int k = 0; k < a; k++)
        if ((1 << k) & j) w.push_back(k), s = k, beg |= 1 << k;
      s++;
      beg |= 1 << s;
      for (int k = (1 << w.size()) - 1; k >= 0; k--) {
        int t = 0, t2 = beg, cnt = 0;
        for (int l = 0; l < w.size(); l++)
          if ((1 << l) & k) t += ar[w[l]], t2 ^= (1 << w[l]), cnt++;
        if (ar[s] - 1 - t <= i) {
          if ((ar[s] - 1 - t) + cnt <= 1) continue;
          dn[i][j] |= dn[i - (ar[s] - 1 - t)][t2];
        }
        if (dn[i][j]) break;
      }
    }
  if (dn[s1][0])
    printf("YES\n");
  else
    printf("NO\n");
  return 0;
}

```