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.
The first line contains integer *n* (1 ≤ *n* ≤ 100) — the number of elements in the array. The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 1000) — the array elements.
#include<bits/stdc++.h>
using namespace std;
#define LIMIT 1000
#define ll long long


int main ()
{
int n;
cin>>n;
int arr[n] ;
set <int> base;
for (int i=0;i <n;i++)
{
    cin>>arr[i];
    base.insert(arr[i]);
}
int big = 1;
for (auto i: base)
{
    int rep = 0;
    for (int j=0;j<n;j++)
    {
        if (arr[j] == i) rep++;
    }
    if (rep>big) big = rep;
}
int valid = 2*big - 1;
if (n >= valid)
    cout<<"YES";
else
    cout<<"NO";


return 0;
}
