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 a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 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.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
mas = list(map(int, input().split()))
mas2 = [0 for _ in range(1001)]
for i in mas:
    mas2[i]+=1
i = 0
for i in mas2:
    if i > (n + 1) / 2:
        print ("NO")
        return
print ("YES")


n = int(input())
A = list(map(int, input().split()))
P = [0] * 1000
for i in range(n):
    P[A[i] - 1] += 1
ans = 0
for i in range(1000):
    if (P[i] > (n + 1) / 2):
        ans = 1
if (ans):
    print("NO")
else:
    print("YES")

from collections import *
n = int(input())
c = Counter()

for i in list(map(int, input().split())):
  c[i] += 1
print("NO" if c.most_common(1)[0][1] > (n + 1) // 2 else "YES")



n = int(input())
lst = [int(x) for x in input().split()]
cur, cnt = 0, 0
for i in lst:
  if i == cur: cnt += 1
  elif cnt == 0: cur, cnt = i, 1
  else: cnt -= 1
cnt = 0
for i in lst:
  if i == cur: cnt += 1
print("YES" if cnt + (cnt - 1) <= n else "NO")


from collections import Counter
n = int(input())
lst = [int(x) for x in input().split()]
c = Counter(lst)
print("YES" if c.most_common(1)[0][1] * 2 - 1 <= n else "NO")


from collections import Counter
n = int(input())
print("YES" if Counter([int(x) for x in input().split()]).most_common(1)[0][1] * 2 - 1 <= n else "NO")


from collections import Counter
n = int(input())
print("YES" if Counter(input().split()).most_common(1)[0][1] * 2 - 1 <= n else "NO")


n=int(input())
s=input().split()
print("YES"if all([s.count(i)*2-1<=n for i in s])else"NO")


3

n = int(input())
a = list(map(int, input().split()))
m = max(len([1 for w in a if w == v]) for v in a)
if 2 * m <= n + 1:
    print("YES")
else:
    print("NO")


n = int(input())
v = list(map(int, input().split()))
sol = 'YES'

for x in v:
    if v.count(x) * 2 > n + 1: sol = 'NO'

print(sol)


n = int(input())
C = [0] * 1001
for x in input().split():
  C[int(x)] += 1
for x in C:
  if x > (n+1)/2:
    print("NO")
    return
print("YES")


import sys
f = sys.stdin
#f = open("input.txt", "r")
n = int(f.readline().strip())
a = [int(i) for i in f.readline().strip().split()]
cnt = dict.fromkeys(a)
for i in cnt:
    cnt[i] = a.count(i)
if (sum(cnt.values()) - max(cnt.values()) < sum(cnt.values())//2 or a.count(a[0]) == len(a)) and len(a) >= 2:
    print("NO")
else:
    print("YES")

while(1):
    try:
        n=int(input())
        a=list(map(int,input().split()))
        b=[]
        for ele in a:
            if ele in b:
                continue
            else:
                b.append(ele)
        c=1
        for ele in b:
            if a.count(ele)<=(n+1)//2:
                continue
            else:
                c=0
                break
        if c==1:
            print("YES")
        else:
            print("NO")
    
    except EOFError:
        break

n = int(input())
a = input().split()
print("YES" if all(a.count(i)*2-1 <= n for i in a) else "NO")

n = (int(input()) + 1) // 2
t, p = input().split(), {}
for i in t:
    p[i] = p.get(i, 0) + 1
print('YNEOS'[max(p.values()) > n:: 2])


n = int(input())
a = list(map(int, input().split()))

b = {}
for i in range(n):
    if a[i] in b:
        b[a[i]] += 1
    else:
        b[a[i]] = 1

if max(b.values()) <= (n+1)//2:
    print('YES')
else:
    print('NO')



n = int(input())
q = [0] * 1005
f = 1
a = list(map(int, input().split()))
for i in range(n):
    q[a[i]] += 1
    if q[a[i]] > n // 2 + (n % 2):
        f = 0
if f:
    print('YES')
else:
    print('NO')

n = int(input())
s = [0]*1001
f = True
t = list(map(int, input().split()))
for i in range(n):
    a = t[i]
    s[a] += 1
for i in range(1001):
    if s[i] > (n + 1) // 2:
        f = False
if f:
    print("YES")
else:
    print("NO")

n=int(input())
a=list(map(int,input().split()))

if(n==1):
    print("YES")
else:
    L={}
    for item in a:
        if(item in L):
            L[item]+=1
        else:
            L[item]=1
    lim=n//2
    if(n%2==1):
        lim+=1
    ans="YES"
    for item in L:
        if(L[item]>lim):
            ans="NO"
    print(ans)


n = int(input())
c = {}
for x in (int(x) for x in input().split()):
    c[x] = 1 if x not in c else c[x] + 1
val = sum(1 for x in c if c[x] > (n + 1) // 2)
print('NO' if val else 'YES')

import sys
import math

n = int(sys.stdin.readline())
an = [int(x) for x in (sys.stdin.readline()).split()]

d = dict()

for i in an:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
        
vmax = 0
vsum = 0
for i in list(d.keys()):
    vsum += d[i]
    if(d[i] > vmax):
        vmax = d[i]
        
if(vsum - vmax >= vmax - 1):
    print("YES")
else:
    print("NO")
    


import sys
import math

n = int(sys.stdin.readline())
an = [int(x) for x in (sys.stdin.readline()).split()]

d = dict()

for i in an:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
        
vmax = 0
#vsum = 0
for i in list(d.keys()):
    #vsum += d[i]
    if(d[i] > vmax):
        vmax = d[i]
        
if(vmax <= (n + 1) / 2):
    print("YES")
else:
    print("NO")
    


from collections import Counter
n = int(input())
cnt = Counter([int(x) for x in input().split()])
print('YES' if cnt.most_common(1)[0][1] <= (n - 1) // 2 + 1 else 'NO')


from collections import Counter


def main():
    n = int(input())
    c = Counter(input().split())
    print(('NO', 'YES')[max(c.values()) * 2 < n + 2])


def __starting_point():
    main()

__starting_point()

def main():
    n = int(input())
    l = [-2] * 1001
    for x in map(int, input().split()):
        l[x] += 2
    print(('NO', 'YES')[max(l) < n])


def __starting_point():
    main()

__starting_point()