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.
import sys

def readints() :
    l = sys.stdin.readline()
    return map(int, l.split(' '))

def readstring() :
    l = sys.stdin.readline()[:-1]
    return l

def readint() :
    l = sys.stdin.readline()
    return int(l)

def clearchars(s, chars) :
    for c in chars :
        s = s.replace(c, '')
    return s

def gcd(a, b) :
    if (a < b ) :
        a, b = b, a
    if b == 0 :
        return a
    return gcd(b, a % b)

def hist(a) :
    h = {}
    for x in a :
        try : 
            h[x] += 1
        except KeyError :
            h[x] = 1
    return h

def lucky(n) :
    s = set(str(n))
    return all(map(lambda x: x in '47', s))    

def yslice(a, j) :
    return map(lambda x: x[j], a)

def dist2(a, b) :
    return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5

def chain_len(a) :
    l = .0
    for d, e in zip(a, a[1:]) :
        l += dist2(d, e)
    return l

def is_prime(x) :
    if x == 1 :
        return False
    sq = int(x ** 0.5) 
    for i in [2] + range(3, sq + 1, 2) :
        if x % i == 0 :
            return False
    return True


digits = '0123456789'

def noe() :
    print "NO"
    exit(0)

def yese() :
    print "YES"
    exit(0)

n = readint()
a = readints()

h = hist(a)
m = sorted(h.itervalues(), reverse = True)[0]
if m - 1 > (n - 1) / 2 :
    noe()
else :
    yese()
