#include <bits/stdc++.h>
using namespace std;
long long int smallestDivisor(long long int n) {
  if (n % 2 == 0) return 2;
  for (long long int i = 3; i * i <= n; i += 2) {
    if (n % i == 0) return i;
  }
  return n;
}
long long int max(long long int a, long long int b) { return a > b ? a : b; }
long long int min(long long int a, long long int b) { return a < b ? a : b; }
long long int gcd(long long int a, long long int b) {
  while (b) {
    long long int t = a;
    a = b;
    b = t % b;
  }
  return a;
}
long long int lcm(long long int a, long long int b) {
  return (max(a, b) / gcd(a, b)) * min(a, b);
}
int cnt[200005] = {0};
vector<int> adj[200005];
map<int, int, greater<int> > factorize(int n) {
  int count = 0;
  map<int, int, greater<int> > fact;
  while (!(n % 2)) {
    n /= 2;
    count++;
  }
  if (count) fact[2] += count;
  for (int i = 3; i <= sqrt(n); i += 2) {
    count = 0;
    while ((n % i) == 0) {
      count++;
      n /= i;
    }
    if (count) fact[i] += count;
  }
  if (n > 2) fact[n]++;
  for (auto it : fact) {
    cnt[it.first]++;
    adj[it.first].push_back(it.second);
  }
  return fact;
}
long long int power(long long int x, int p) {
  if (p == 0) return 1;
  long long int ans = power(x, p / 2);
  ans = ans * ans;
  if (p % 2 == 1) ans = ans * x;
  return ans;
}
bool isPrime(long long int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
vector<long long int> countDivisors(long long int n) {
  long long int cnt = 0;
  std::vector<long long int> v;
  for (long long int i = 1; i <= sqrt(n); i++) {
    if (n % i == 0) {
      v.push_back(i);
      if (n / i == i)
        cnt++;
      else {
        cnt = cnt + 2;
        v.push_back(n / i);
      }
    }
  }
  return v;
}
bool isPowerOfTwo(long long int x) { return (x && !(x & (x - 1))); }
map<long long int, long long int> factors(long long int n) {
  vector<long long int> f;
  map<long long int, long long int> m;
  for (long long int x = 2; x * x <= n; x++) {
    while (n % x == 0) {
      f.push_back(x);
      m[x]++;
      n /= x;
    }
  }
  if (n > 1) {
    f.push_back(n);
    m[n]++;
  }
  return m;
}
bool cmp(pair<long long int, long long int> v1,
         pair<long long int, long long int> v2) {
  if (v1.first > v2.first) {
    return true;
  } else if (v1.first < v2.first) {
    return false;
  } else {
    return v1.second < v2.second;
  }
}
long long int binarySearch(long long int arr[], long long int l,
                           long long int r, long long int x) {
  if (r >= l) {
    long long int mid = l + (r - l) / 2;
    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x);
    return binarySearch(arr, mid + 1, r, x);
  }
  return -1;
}
int rub[2000001];
bool ispali(int n) {
  int no = n;
  int rev = 0;
  while (no > 0) {
    int ld = no % 10;
    no /= 10;
    rev = rev * 10 + ld;
  }
  if (n == rev)
    return true;
  else
    return false;
}
void np() {
  for (int i = 1; i <= 2000000; i++) {
    if (ispali(i))
      rub[i] = rub[i - 1] + 1;
    else
      rub[i] = rub[i - 1];
  }
}
int pi[20000001];
bool isprime[20000001];
void seive() {
  for (int i = 4; i <= 20000000; i += 2) isprime[i] = 1;
  for (int i = 3; i * i <= 20000000; i += 2) {
    if (!isprime[i]) {
      for (int j = i * i; j <= 20000000; j += i) isprime[j] = 1;
    }
  }
  for (int i = 2; i <= 20000000; i++) {
    if (!isprime[i])
      pi[i] = pi[i - 1] + 1;
    else
      pi[i] = pi[i - 1];
  }
}
int g1;
void bfs(vector<vector<int> > &g, int pos, vector<int> visited) {
  queue<int> q;
  q.push(pos);
  while (q.size() > 0) {
    if (q.front() == g1) {
      cout << "yes";
      return;
    }
    int i = q.front();
    q.pop();
    visited[i] = 1;
    for (int j = 0; j < g[i].size(); j++) {
      if (visited[g[i][j]] == 0) {
        q.push(g[i][j]);
        visited[g[i][j]] = 1;
      }
    }
  }
  return;
}
void pairsort(long long int a[], long long int b[], long long int n) {
  pair<long long int, long long int> pairt[n];
  for (long long int i = 0; i < n; i++) {
    pairt[i].first = a[i];
    pairt[i].second = b[i];
  }
  sort(pairt, pairt + n);
  for (long long int i = 0; i < n; i++) {
    a[i] = pairt[i].first;
    b[i] = pairt[i].second;
  }
}
long long int modpower(long long int x, long long int y, long long int p) {
  long long int res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long int modsum(long long int a, long long int b, long long int m) {
  return ((a % m) + (b % m)) % m;
}
long long int modmul(long long int a, long long int b, long long int m) {
  return ((a % m) * (b % m)) % m;
}
long long int modInverse(long long int a, long long int m) {
  return modpower(a, m - 2, m);
}
vector<long long int> factorial() {
  int i;
  vector<long long int> fact(200002 + 1, 0);
  fact[0] = 1;
  for (i = 1; i <= 200002; i++) fact[i] = (fact[i - 1] * i) % 1000000007;
  return fact;
}
long long int highestPowerof2(long long int n) {
  long long int p = (long long int)log2(n);
  return (long long int)pow(2, p);
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t1 = 1;
  while (t1--) {
    long long int n;
    cin >> n;
    long long int a[n];
    for (long long int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    for (long long int i = 0; i < n - 1; i++) {
      if (a[i + 1] - a[i] > 1) {
        cout << "NO";
        return 0;
      }
    }
    map<int, int> cnt;
    for (long long int i = 0; i < n; i++) cnt[a[i]]++;
    map<int, int>::iterator it = cnt.begin();
    int cur = (*it).first, ct = 2 * (*it).second;
    it++;
    bool f = 1;
    while (it != cnt.end()) {
      if ((*it).first - cur > 1) {
        f = 0;
        break;
      }
      if (ct == 0) {
        f = 0;
        break;
      }
      ct = 2 * (*it).second - ct;
      if (ct < 0) {
        f = 0;
        break;
      }
      cur = (*it).first;
      it++;
    }
    if (ct || !f)
      cout << "NO"
           << "\n";
    else
      cout << "YES"
           << "\n";
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

One day Anna got the following task at school: to arrange several numbers in a circle so that any two neighboring numbers differs exactly by 1. Anna was given several numbers and arranged them in a circle to fulfill the task. Then she wanted to check if she had arranged the numbers correctly, but at this point her younger sister Maria came and shuffled all numbers. Anna got sick with anger but what's done is done and the results of her work had been destroyed. But please tell Anna: could she have hypothetically completed the task using all those given numbers?

Input

The first line contains an integer n — how many numbers Anna had (3 ≤ n ≤ 105). The next line contains those numbers, separated by a space. All numbers are integers and belong to the range from 1 to 109.

Output

Print the single line "YES" (without the quotes), if Anna could have completed the task correctly using all those numbers (using all of them is necessary). If Anna couldn't have fulfilled the task, no matter how hard she would try, print "NO" (without the quotes).

Examples

Input

4
1 2 3 2


Output

YES


Input

6
1 1 2 2 2 3


Output

YES


Input

6
2 4 1 1 2 2


Output

NO

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long int smallestDivisor(long long int n) {
  if (n % 2 == 0) return 2;
  for (long long int i = 3; i * i <= n; i += 2) {
    if (n % i == 0) return i;
  }
  return n;
}
long long int max(long long int a, long long int b) { return a > b ? a : b; }
long long int min(long long int a, long long int b) { return a < b ? a : b; }
long long int gcd(long long int a, long long int b) {
  while (b) {
    long long int t = a;
    a = b;
    b = t % b;
  }
  return a;
}
long long int lcm(long long int a, long long int b) {
  return (max(a, b) / gcd(a, b)) * min(a, b);
}
int cnt[200005] = {0};
vector<int> adj[200005];
map<int, int, greater<int> > factorize(int n) {
  int count = 0;
  map<int, int, greater<int> > fact;
  while (!(n % 2)) {
    n /= 2;
    count++;
  }
  if (count) fact[2] += count;
  for (int i = 3; i <= sqrt(n); i += 2) {
    count = 0;
    while ((n % i) == 0) {
      count++;
      n /= i;
    }
    if (count) fact[i] += count;
  }
  if (n > 2) fact[n]++;
  for (auto it : fact) {
    cnt[it.first]++;
    adj[it.first].push_back(it.second);
  }
  return fact;
}
long long int power(long long int x, int p) {
  if (p == 0) return 1;
  long long int ans = power(x, p / 2);
  ans = ans * ans;
  if (p % 2 == 1) ans = ans * x;
  return ans;
}
bool isPrime(long long int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
vector<long long int> countDivisors(long long int n) {
  long long int cnt = 0;
  std::vector<long long int> v;
  for (long long int i = 1; i <= sqrt(n); i++) {
    if (n % i == 0) {
      v.push_back(i);
      if (n / i == i)
        cnt++;
      else {
        cnt = cnt + 2;
        v.push_back(n / i);
      }
    }
  }
  return v;
}
bool isPowerOfTwo(long long int x) { return (x && !(x & (x - 1))); }
map<long long int, long long int> factors(long long int n) {
  vector<long long int> f;
  map<long long int, long long int> m;
  for (long long int x = 2; x * x <= n; x++) {
    while (n % x == 0) {
      f.push_back(x);
      m[x]++;
      n /= x;
    }
  }
  if (n > 1) {
    f.push_back(n);
    m[n]++;
  }
  return m;
}
bool cmp(pair<long long int, long long int> v1,
         pair<long long int, long long int> v2) {
  if (v1.first > v2.first) {
    return true;
  } else if (v1.first < v2.first) {
    return false;
  } else {
    return v1.second < v2.second;
  }
}
long long int binarySearch(long long int arr[], long long int l,
                           long long int r, long long int x) {
  if (r >= l) {
    long long int mid = l + (r - l) / 2;
    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x);
    return binarySearch(arr, mid + 1, r, x);
  }
  return -1;
}
int rub[2000001];
bool ispali(int n) {
  int no = n;
  int rev = 0;
  while (no > 0) {
    int ld = no % 10;
    no /= 10;
    rev = rev * 10 + ld;
  }
  if (n == rev)
    return true;
  else
    return false;
}
void np() {
  for (int i = 1; i <= 2000000; i++) {
    if (ispali(i))
      rub[i] = rub[i - 1] + 1;
    else
      rub[i] = rub[i - 1];
  }
}
int pi[20000001];
bool isprime[20000001];
void seive() {
  for (int i = 4; i <= 20000000; i += 2) isprime[i] = 1;
  for (int i = 3; i * i <= 20000000; i += 2) {
    if (!isprime[i]) {
      for (int j = i * i; j <= 20000000; j += i) isprime[j] = 1;
    }
  }
  for (int i = 2; i <= 20000000; i++) {
    if (!isprime[i])
      pi[i] = pi[i - 1] + 1;
    else
      pi[i] = pi[i - 1];
  }
}
int g1;
void bfs(vector<vector<int> > &g, int pos, vector<int> visited) {
  queue<int> q;
  q.push(pos);
  while (q.size() > 0) {
    if (q.front() == g1) {
      cout << "yes";
      return;
    }
    int i = q.front();
    q.pop();
    visited[i] = 1;
    for (int j = 0; j < g[i].size(); j++) {
      if (visited[g[i][j]] == 0) {
        q.push(g[i][j]);
        visited[g[i][j]] = 1;
      }
    }
  }
  return;
}
void pairsort(long long int a[], long long int b[], long long int n) {
  pair<long long int, long long int> pairt[n];
  for (long long int i = 0; i < n; i++) {
    pairt[i].first = a[i];
    pairt[i].second = b[i];
  }
  sort(pairt, pairt + n);
  for (long long int i = 0; i < n; i++) {
    a[i] = pairt[i].first;
    b[i] = pairt[i].second;
  }
}
long long int modpower(long long int x, long long int y, long long int p) {
  long long int res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long int modsum(long long int a, long long int b, long long int m) {
  return ((a % m) + (b % m)) % m;
}
long long int modmul(long long int a, long long int b, long long int m) {
  return ((a % m) * (b % m)) % m;
}
long long int modInverse(long long int a, long long int m) {
  return modpower(a, m - 2, m);
}
vector<long long int> factorial() {
  int i;
  vector<long long int> fact(200002 + 1, 0);
  fact[0] = 1;
  for (i = 1; i <= 200002; i++) fact[i] = (fact[i - 1] * i) % 1000000007;
  return fact;
}
long long int highestPowerof2(long long int n) {
  long long int p = (long long int)log2(n);
  return (long long int)pow(2, p);
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t1 = 1;
  while (t1--) {
    long long int n;
    cin >> n;
    long long int a[n];
    for (long long int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    for (long long int i = 0; i < n - 1; i++) {
      if (a[i + 1] - a[i] > 1) {
        cout << "NO";
        return 0;
      }
    }
    map<int, int> cnt;
    for (long long int i = 0; i < n; i++) cnt[a[i]]++;
    map<int, int>::iterator it = cnt.begin();
    int cur = (*it).first, ct = 2 * (*it).second;
    it++;
    bool f = 1;
    while (it != cnt.end()) {
      if ((*it).first - cur > 1) {
        f = 0;
        break;
      }
      if (ct == 0) {
        f = 0;
        break;
      }
      ct = 2 * (*it).second - ct;
      if (ct < 0) {
        f = 0;
        break;
      }
      cur = (*it).first;
      it++;
    }
    if (ct || !f)
      cout << "NO"
           << "\n";
    else
      cout << "YES"
           << "\n";
  }
  return 0;
}

```