#include <bits/stdc++.h>
using namespace std;
const int inf = 2000000000;
static inline int Rint() {
  struct X {
    int dig[256];
    X() {
      for (int i = '0'; i <= '9'; ++i) dig[i] = 1;
      dig['-'] = 1;
    }
  };
  static X fuck;
  int s = 1, v = 0, c;
  for (; !fuck.dig[c = getchar()];)
    ;
  if (c == '-')
    s = 0;
  else if (fuck.dig[c])
    v = c ^ 48;
  for (; fuck.dig[c = getchar()]; v = v * 10 + (c ^ 48))
    ;
  return s ? v : -v;
}
template <typename T>
static inline void cmax(T& a, const T& b) {
  if (b > a) a = b;
}
template <typename T>
static inline void cmin(T& a, const T& b) {
  if (b < a) a = b;
}
int cnt[26];
int data[26];
int top;
int dfs(int curr);
int make(int dest, int last, int used, int curr) {
  if (dest == 0) {
    if (used > 1) {
      ++cnt[data[curr]];
      if (dfs(curr + 1)) return 1;
      --cnt[data[curr]];
      return 0;
    } else {
      return 0;
    }
  }
  for (int i = last; i >= 1; --i)
    if (cnt[i]) {
      for (int j = 1; j * i <= dest && j <= cnt[i]; ++j) {
        cnt[i] -= j;
        if (make(dest - j * i, i - 1, used + j, curr)) {
          return 1;
        }
        cnt[i] += j;
      }
    }
  return 0;
}
int dfs(int curr) {
  if (curr == top) return accumulate(cnt, cnt + 25, 0) == 1;
  return make(data[curr] - 1, 24, 0, curr);
}
int main() {
  int n = Rint();
  for (int i = (0); i < (n); ++i) data[i] = Rint();
  sort(data, data + n);
  int curr = 0;
  while (curr < n && data[curr] == 1) ++cnt[1], ++curr;
  top = 0;
  while (curr < n) data[top++] = data[curr++];
  if (top == 0) {
    int total = accumulate(cnt, cnt + 25, 0);
    if (total == 1)
      puts("YES");
    else
      puts("NO");
    return 0;
  }
  if (data[top - 1] != n) {
    puts("NO");
    return 0;
  }
  if (dfs(0))
    puts("YES");
  else
    puts("NO");
  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;
const int inf = 2000000000;
static inline int Rint() {
  struct X {
    int dig[256];
    X() {
      for (int i = '0'; i <= '9'; ++i) dig[i] = 1;
      dig['-'] = 1;
    }
  };
  static X fuck;
  int s = 1, v = 0, c;
  for (; !fuck.dig[c = getchar()];)
    ;
  if (c == '-')
    s = 0;
  else if (fuck.dig[c])
    v = c ^ 48;
  for (; fuck.dig[c = getchar()]; v = v * 10 + (c ^ 48))
    ;
  return s ? v : -v;
}
template <typename T>
static inline void cmax(T& a, const T& b) {
  if (b > a) a = b;
}
template <typename T>
static inline void cmin(T& a, const T& b) {
  if (b < a) a = b;
}
int cnt[26];
int data[26];
int top;
int dfs(int curr);
int make(int dest, int last, int used, int curr) {
  if (dest == 0) {
    if (used > 1) {
      ++cnt[data[curr]];
      if (dfs(curr + 1)) return 1;
      --cnt[data[curr]];
      return 0;
    } else {
      return 0;
    }
  }
  for (int i = last; i >= 1; --i)
    if (cnt[i]) {
      for (int j = 1; j * i <= dest && j <= cnt[i]; ++j) {
        cnt[i] -= j;
        if (make(dest - j * i, i - 1, used + j, curr)) {
          return 1;
        }
        cnt[i] += j;
      }
    }
  return 0;
}
int dfs(int curr) {
  if (curr == top) return accumulate(cnt, cnt + 25, 0) == 1;
  return make(data[curr] - 1, 24, 0, curr);
}
int main() {
  int n = Rint();
  for (int i = (0); i < (n); ++i) data[i] = Rint();
  sort(data, data + n);
  int curr = 0;
  while (curr < n && data[curr] == 1) ++cnt[1], ++curr;
  top = 0;
  while (curr < n) data[top++] = data[curr++];
  if (top == 0) {
    int total = accumulate(cnt, cnt + 25, 0);
    if (total == 1)
      puts("YES");
    else
      puts("NO");
    return 0;
  }
  if (data[top - 1] != n) {
    puts("NO");
    return 0;
  }
  if (dfs(0))
    puts("YES");
  else
    puts("NO");
  return 0;
}

```