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
import math
from sys import stdin, stdout
 
# Most Frequently Used Number Theory Concepts
# SOE(helper function of get gcd)
def sieve(N):
    primeNumbers = [True]*(N+1)
    primeNumbers[0] = False
    primeNumbers[1] = False
    i = 2
    while i*i <= N:
        j = i
        if primeNumbers[j]:
            while j*i <= N:
                primeNumbers[j*i] = False
                j += 1
        i += 1
    return primeNumbers
 
# get prime number form 1 to N
def getPrime(N):
    primes = sieve(N)
    result = []
    for i in range(len(primes)):
        if primes[i]:
            result.append(i)
    return result
 
# factors of n
def factor(N):
    factors = []
    i = 1
    while i*i <= N:
        if N % i == 0:
            factors.append(i)
            if i != N//i:
                factors.append(N//i)
        i += 1
    return sorted(factors)
 
# reduce a string in number under range(1000000007)
def reduceB(b) : 
    # Initialize result 
    mod = 0
    # Calculating mod of b with a 
    # to make b like 0 <= b < a 
    for i in range(0, len(b)) : 
        mod = (mod * 10 + ord(b[i])) % 1000000007 
        # print(b[i], ord(b[i]), mod)
    return mod	 # return modulo 
 
# gcd of two numbers
def gcd(a, b):
    if a < b:
        return gcd(b, a)
    if b == 0:
        return a
    return gcd(b, a % b)
 
# TAKE INPUT
def get_ints_in_variables():
    return map(int, sys.stdin.readline().strip().split())
def get_int(): return int(input())
def get_ints_in_list(): return list(
    map(int, sys.stdin.readline().strip().split()))
def get_list_of_list(n): return [list(
    map(int, sys.stdin.readline().strip().split())) for _ in range(n)]
def get_string(): return sys.stdin.readline().strip()

def arrSame(arr, n):
    for i in range(1, n):
        if arr[0] != arr[i+1]:
            return False
    return True
 
def main():
    # Write Your Code Here
    n = int(input())
    arr = get_ints_in_list()
    mp = {}
    for i in range(0, n):
        if arr[i] not in mp:
            mp[arr[i]] = 1
        else:
            mp[arr[i]] += 1
    
    mx = 0
    for key, value in mp.items():
        if mx < value:
            mx = value
    diff = n-mx
    if mx <= diff+1:
        print("YES")
    else:
        print("NO")


# for printing format
# print("Case #{}: {}".format(t+1, ans))
#  calling main Function
if __name__ == "__main__":
    main()