Yaroslav has an array that consists of n integers. In one second Yaroslav can swap two neighboring array elements. Now Yaroslav is wondering if he can obtain an array where any two neighboring elements would be distinct in a finite time.

Help Yaroslav.

Input

The first line contains integer n (1 ≤ n ≤ 100) — the number of elements in the array. The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1000) — the array elements.

Output

In the single line print "YES" (without the quotes) if Yaroslav can obtain the array he needs, and "NO" (without the quotes) otherwise.

Examples

Input

1
1


Output

YES


Input

3
1 1 2


Output

YES


Input

4
7 7 7 7


Output

NO

Note

In the first sample the initial array fits well.

In the second sample Yaroslav can get array: 1, 2, 1. He can swap the last and the second last elements to obtain it.

In the third sample Yarosav can't get the array he needs.
#include <bits/stdc++.h>
using namespace std;
class Utl {
 public:
  template <class mixed>
  static void print(mixed value) {
    std::cout << value;
  }
  template <class mixed, class padd>
  static void print(mixed prefix, padd suffix) {
    std::cout << prefix << suffix;
  }
  template <class mixed>
  static void print(mixed value, bool space) {
    if (space)
      std::cout << value << " ";
    else
      std::cout << value;
  }
  template <class mixed>
  static void println(mixed value) {
    std::cout << value << std::endl;
  }
  static void println() { std::cout << endl; }
  template <class mixed>
  static void log(vector<mixed> arr, bool nl = false) {
    for (int i = 0; i <= arr.size() - 1; i++) Utl::print(arr[i], " ");
    if (nl) Utl::println();
  }
  template <class mixed>
  static void log(mixed arr[], int len, bool nl = false) {
    for (int i = 0; i <= len - 1; i++) Utl::print(arr[i], " ");
    if (nl) Utl::println();
  }
  template <class mixed>
  static vector<mixed> sort(vector<mixed> vec, int dir = 0) {
    if (dir == 1)
      std::sort(vec.begin(), vec.end(), greater<mixed>());
    else
      std::sort(vec.begin(), vec.end());
    return vec;
  }
  static vector<int> sort(vector<int> vec, std::function<bool(int, int)> dir) {
    std::sort(vec.begin(), vec.end(), dir);
    return vec;
  }
  static vector<char> split(string str) {
    vector<char> vec;
    for (int i = 0; i < str.size(); i++) vec.push_back(str[i]);
    return vec;
  }
  template <class mixed>
  static mixed min(vector<mixed> vec) {
    return *min_element(vec.begin(), vec.end());
  }
  template <class mixed>
  static mixed max(vector<mixed> vec) {
    return *max_element(vec.begin(), vec.end());
  }
  template <class mixed>
  static mixed sum(vector<mixed> vec) {
    return accumulate(vec.begin(), vec.end(), 0);
  }
  template <class mixed>
  static vector<mixed> reverse(vector<mixed> vec) {
    std::reverse(vec.begin(), vec.end());
    return vec;
  }
  template <class mixed>
  static bool every(vector<mixed> vec,
                    std::function<bool(const mixed)> callback) {
    return all_of(vec.begin(), vec.end(), callback);
  }
  template <class mixed>
  static bool some(vector<mixed> vec,
                   std::function<bool(const mixed)> callback) {
    return any_of(vec.begin(), vec.end(), callback);
  }
  template <class mixed>
  static vector<mixed> map(vector<mixed> vec,
                           std::function<mixed(const mixed)> callback) {
    vector<mixed> ret;
    for (auto &el : vec) ret.push_back(callback(el));
    return ret;
  }
  template <class mixed>
  static vector<mixed> filter(vector<mixed> vec,
                              std::function<mixed(const mixed)> callback) {
    vector<mixed> ret;
    for (auto &el : vec) {
      if (callback(el)) ret.push_back(el);
    }
    return ret;
  }
  static string toString(int num) { return to_string(num); }
  static int parseInt(string num) { return stoi(num); }
};
int gcd(int a, int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
void solve() {
  int n;
  cin >> n;
  map<int, int> hash;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    hash[x]++;
  }
  int c = (n + 1) / 2;
  bool ans = true;
  for (auto &it : hash) {
    if (it.second > c) {
      ans = false;
      break;
    }
  }
  cout << (ans ? "YES" : "NO") << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  while (t--) solve();
  return 0;
}
