#include <bits/stdc++.h>
using namespace std;
int N;
int C[24];
bool dp[13][1 << 12][23];
int sm[1 << 12];
int bc[1 << 12];
int main() {
  scanf("%d", &N);
  for (int(i) = 0; (i) < (N); (i)++) scanf("%d", &C[i]);
  sort(C, C + N);
  for (int(i) = 0; (i) < (N); (i)++)
    if (C[i] == 2) return puts("NO"), 0;
  if (C[N - 1] != N) return puts("NO"), 0;
  if (N == 1 && C[0] == 1) return puts("YES"), 0;
  vector<int> v;
  int c1 = 0;
  for (int(i) = 0; (i) < (N); (i)++) {
    if (C[i] == 1)
      c1++;
    else
      v.push_back(C[i]);
  }
  sort((v).begin(), (v).end());
  reverse((v).begin(), (v).end());
  if (c1 < N / 2) return puts("NO"), 0;
  int n = v.size();
  dp[0][1][c1] = true;
  for (int(i) = 0; (i) < (1 << n); (i)++)
    for (int(j) = 0; (j) < (n); (j)++)
      sm[i] += v[j] * (i >> j & 1), bc[i] += (i >> j & 1);
  for (int(i) = 0; (i) < (n); (i)++)
    for (int(b) = 0; (b) < (1 << n); (b)++)
      for (int(j) = 0; (j) < (c1 + 1); (j)++)
        if (dp[i][b][j] && (b >> i & 1))
          for (int(k) = 0; (k) < (1 << n); (k)++)
            if ((b & k) == 0 && v[i] - 1 >= sm[k] && v[i] - 1 - sm[k] <= j &&
                (v[i] - 1 - sm[k] + bc[k]) > 1)
              dp[i + 1][b | k][j - (v[i] - 1 - sm[k])] = true;
  return puts(dp[n][(1 << n) - 1][0] ? "YES" : "NO");
}

### 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;
int N;
int C[24];
bool dp[13][1 << 12][23];
int sm[1 << 12];
int bc[1 << 12];
int main() {
  scanf("%d", &N);
  for (int(i) = 0; (i) < (N); (i)++) scanf("%d", &C[i]);
  sort(C, C + N);
  for (int(i) = 0; (i) < (N); (i)++)
    if (C[i] == 2) return puts("NO"), 0;
  if (C[N - 1] != N) return puts("NO"), 0;
  if (N == 1 && C[0] == 1) return puts("YES"), 0;
  vector<int> v;
  int c1 = 0;
  for (int(i) = 0; (i) < (N); (i)++) {
    if (C[i] == 1)
      c1++;
    else
      v.push_back(C[i]);
  }
  sort((v).begin(), (v).end());
  reverse((v).begin(), (v).end());
  if (c1 < N / 2) return puts("NO"), 0;
  int n = v.size();
  dp[0][1][c1] = true;
  for (int(i) = 0; (i) < (1 << n); (i)++)
    for (int(j) = 0; (j) < (n); (j)++)
      sm[i] += v[j] * (i >> j & 1), bc[i] += (i >> j & 1);
  for (int(i) = 0; (i) < (n); (i)++)
    for (int(b) = 0; (b) < (1 << n); (b)++)
      for (int(j) = 0; (j) < (c1 + 1); (j)++)
        if (dp[i][b][j] && (b >> i & 1))
          for (int(k) = 0; (k) < (1 << n); (k)++)
            if ((b & k) == 0 && v[i] - 1 >= sm[k] && v[i] - 1 - sm[k] <= j &&
                (v[i] - 1 - sm[k] + bc[k]) > 1)
              dp[i + 1][b | k][j - (v[i] - 1 - sm[k])] = true;
  return puts(dp[n][(1 << n) - 1][0] ? "YES" : "NO");
}

```