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.
def num_check(num_list, num_cnt):
    global flag
    global list_of_numbers
    
    num_list = num_list.split(' ')
    if len(num_list) != num_cnt:
        print('\nNumber list out of bounds. Expected {} numbers.'.format(num_cnt))
        return
    for i in num_list:
        if '.' in i:
            print('\nEnter an integer.\n')
            return
        try:
            num = int(i)
            if num not in list_of_numbers.keys():
                list_of_numbers[num] = 1
            else:
                list_of_numbers[num] += 1
        except:
            if i != ' ':
                print('\nEnter the numbers separated by a space.')
                return
            else:
                pass
    flag = 1
    
def selection_sort():
    global list_of_numbers
    
    list_of_numbers = list(list_of_numbers.items())
    for i in range(len(list_of_numbers)-1):
        for j in range(i+1, len(list_of_numbers)):
            if list_of_numbers[i][1] < list_of_numbers[j][1]:
                list_of_numbers[j], list_of_numbers[i] = list_of_numbers[i], list_of_numbers[j]

if __name__ == '__main__':
    flag = 0
    list_of_numbers = {}
    num_cnt = int(input())
    while flag == 0:
        num_list = input()
        num_check(num_list, num_cnt)
    selection_sort()
    
    highest_freq = list_of_numbers[0][1]
    if num_cnt-highest_freq >= round(num_cnt//2):
        print('YES')
    else:
        print('NO')