#include <bits/stdc++.h>
using namespace std;
inline int toMask(int x) { return (1 << x) - 1; }
inline int appendToMask(int mask, int number) {
  if (number == 0) return mask;
  return (mask << number + 1) | toMask(number);
}
inline int leavesBits(int mask) {
  int bits = 0;
  while ((mask & (3 << bits)) != 0) {
    bits++;
  }
  return bits;
}
void iterateTheMask(int mask, function<void(int, int)> action) {
  int processed = 0;
  int processedBits = 0;
  while (mask > 0) {
    int nextNumber = 0;
    while (mask % 2 == 1) {
      nextNumber++;
      mask /= 2;
    }
    mask /= 2;
    if (processed != 0) {
      action(nextNumber, (mask << processedBits) + processed);
    } else {
      action(nextNumber, mask);
    }
    processed = appendToMask(processed, nextNumber);
    processedBits += nextNumber;
    if (processedBits != nextNumber) processedBits++;
  }
}
struct MutableInt {
  int x;
};
bool madeByOnes(int mask, int howManyOnes) {
  MutableInt actualOnes;
  actualOnes.x = 0;
  int lb = leavesBits(mask);
  iterateTheMask(mask & toMask(lb), [&](int number, int rem) {
    if (number == 1) {
      actualOnes.x += howManyOnes + 1;
    } else {
      actualOnes.x += number;
    }
  });
  iterateTheMask(mask >> lb + 2,
                 [&](int number, int rem) { actualOnes.x += number; });
  return actualOnes.x == howManyOnes;
}
const int MAX_MASK = 1 << 25;
bool dp[2][MAX_MASK];
int main() {
  int n;
  cin >> n;
  int treeSizes[24];
  for (int i = 0; i < n; i++) {
    cin >> treeSizes[i];
  }
  sort(treeSizes, treeSizes + n);
  int root = n - 1;
  dp[root & 1][toMask(treeSizes[root] - 1)] = true;
  for (int tree = root - 1; tree >= 0; tree--) {
    int treeIndex = tree % 2;
    int treeSize = treeSizes[tree];
    if (treeSize == 1) {
      for (int mask = 0; mask < MAX_MASK; mask++) {
        if (dp[tree + 1 & 1][mask] && madeByOnes(mask, tree + 1)) {
          cout << "YES";
          return 0;
        }
      }
      cout << "NO";
      return 0;
    }
    for (int j = 0; j < MAX_MASK; j++) {
      dp[treeIndex][j] = false;
    }
    for (int mask = 0; mask < MAX_MASK; mask++) {
      if (dp[tree + 1 & 1][mask]) {
        int lb = leavesBits(mask);
        int leavesMask = mask & (1 << lb) - 1;
        int innerMask = mask >> lb + 2;
        iterateTheMask(leavesMask, [&](int number, int rem) {
          if (number > treeSize) {
            int newInner = appendToMask(innerMask, number - treeSize);
            int newLeaves = appendToMask(rem, treeSize - 1);
            int nlb = lb - number + treeSize - 1;
            int newMask = (newInner << nlb + 2) + newLeaves;
            dp[treeIndex][newMask] = true;
          }
        });
        iterateTheMask(innerMask, [&](int number, int rem) {
          if (number >= treeSize) {
            int newInner = appendToMask(rem, number - treeSize);
            int newLeaves = appendToMask(leavesMask, treeSize - 1);
            int nlb = lb == 0 ? treeSize - 1 : lb + treeSize;
            int newMask = (newInner << nlb + 2) + newLeaves;
            dp[treeIndex][newMask] = true;
          }
        });
      }
    }
  }
  cout << (dp[0][0] ? "YES" : "NO");
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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;
inline int toMask(int x) { return (1 << x) - 1; }
inline int appendToMask(int mask, int number) {
  if (number == 0) return mask;
  return (mask << number + 1) | toMask(number);
}
inline int leavesBits(int mask) {
  int bits = 0;
  while ((mask & (3 << bits)) != 0) {
    bits++;
  }
  return bits;
}
void iterateTheMask(int mask, function<void(int, int)> action) {
  int processed = 0;
  int processedBits = 0;
  while (mask > 0) {
    int nextNumber = 0;
    while (mask % 2 == 1) {
      nextNumber++;
      mask /= 2;
    }
    mask /= 2;
    if (processed != 0) {
      action(nextNumber, (mask << processedBits) + processed);
    } else {
      action(nextNumber, mask);
    }
    processed = appendToMask(processed, nextNumber);
    processedBits += nextNumber;
    if (processedBits != nextNumber) processedBits++;
  }
}
struct MutableInt {
  int x;
};
bool madeByOnes(int mask, int howManyOnes) {
  MutableInt actualOnes;
  actualOnes.x = 0;
  int lb = leavesBits(mask);
  iterateTheMask(mask & toMask(lb), [&](int number, int rem) {
    if (number == 1) {
      actualOnes.x += howManyOnes + 1;
    } else {
      actualOnes.x += number;
    }
  });
  iterateTheMask(mask >> lb + 2,
                 [&](int number, int rem) { actualOnes.x += number; });
  return actualOnes.x == howManyOnes;
}
const int MAX_MASK = 1 << 25;
bool dp[2][MAX_MASK];
int main() {
  int n;
  cin >> n;
  int treeSizes[24];
  for (int i = 0; i < n; i++) {
    cin >> treeSizes[i];
  }
  sort(treeSizes, treeSizes + n);
  int root = n - 1;
  dp[root & 1][toMask(treeSizes[root] - 1)] = true;
  for (int tree = root - 1; tree >= 0; tree--) {
    int treeIndex = tree % 2;
    int treeSize = treeSizes[tree];
    if (treeSize == 1) {
      for (int mask = 0; mask < MAX_MASK; mask++) {
        if (dp[tree + 1 & 1][mask] && madeByOnes(mask, tree + 1)) {
          cout << "YES";
          return 0;
        }
      }
      cout << "NO";
      return 0;
    }
    for (int j = 0; j < MAX_MASK; j++) {
      dp[treeIndex][j] = false;
    }
    for (int mask = 0; mask < MAX_MASK; mask++) {
      if (dp[tree + 1 & 1][mask]) {
        int lb = leavesBits(mask);
        int leavesMask = mask & (1 << lb) - 1;
        int innerMask = mask >> lb + 2;
        iterateTheMask(leavesMask, [&](int number, int rem) {
          if (number > treeSize) {
            int newInner = appendToMask(innerMask, number - treeSize);
            int newLeaves = appendToMask(rem, treeSize - 1);
            int nlb = lb - number + treeSize - 1;
            int newMask = (newInner << nlb + 2) + newLeaves;
            dp[treeIndex][newMask] = true;
          }
        });
        iterateTheMask(innerMask, [&](int number, int rem) {
          if (number >= treeSize) {
            int newInner = appendToMask(rem, number - treeSize);
            int newLeaves = appendToMask(leavesMask, treeSize - 1);
            int nlb = lb == 0 ? treeSize - 1 : lb + treeSize;
            int newMask = (newInner << nlb + 2) + newLeaves;
            dp[treeIndex][newMask] = true;
          }
        });
      }
    }
  }
  cout << (dp[0][0] ? "YES" : "NO");
  return 0;
}

```