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.

# Author: SaykaT
# Problem: 296A
# Time Created: July 17(Friday) 2020 || 12:00:24
from math import ceil
from collections import Counter

#>-------------------------<#

# Helper Functions. -> Don't cluster your code.
def check_distinct(ls):
    if len(ls) == 1:
        return 'YES'
    else:
        if len(ls) == 2 and (ls[0] != ls[1]):
            return 'YES'
        elif len(ls) == 2 and (ls[0] == ls[1]):
            return 'NO'
        else:
            ans = 'YES'
            for i in range(len(ls) - 1):
                if ls[i] == ls[i+1]:
                    ans = 'NO'
                    break
            return ans

def check_dis(ls, counted):
    if len(ls) == 1:
        return 'YES'
    else:
        ans = 'YES'
        for key in counted:
            if counted[key] > ceil(len(ls)/ 2):
                ans = 'NO'
                break
        return ans


# IO Functions. -> Input output
def io():
    n = int(input())
    ls = list(map(int, input().split()))
    return [n, ls]

# Main functions. -> Write the main solution here
def solve():
    n, ls = io()
    counted = Counter(ls)
    ans = []
    print(check_dis(ls, counted))
#    while len(ans) != n:
#        for key in counted:
#            if counted[key] != 0:
#                ans.append(key)
#                counted[key] = counted[key] - 1
#    print(ans)
#    print(check_distinct(ans))

# Multiple test cases. -> When you have T test cases.
solve()
    
