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.
# https://codeforces.com/problemset/problem/296/A

"""
Array of n integers
We can swap two neighbouring elements

Is it possible to get an array where an neighbouring elements are distinct

First we claim that it is possible to get to any permutation by swapping consecutive elements.
We can do this via induction. If our array is size 1 we are done.
Suppose we have k elements and we can achieve any permutation via consecutive swaps
Now consider k+1 elements. We can achieve any permutation by going through all permutations
and then moving the k+1th element in the k+2 possible positions. (In the same way bubble sort)

Or we can just think of constructively. So fix the permutation and then in a bubble sort fashion
Put the first element in the first spot and repeat.

Clearly it is impossible to obtain the required condition if a given element
comprises more than half. Now we want to check if it is possible given all elements represent less than half
"""
from collections import Counter
from math import ceil


def main():

    n = int(input())
    a = input().split()

    number_count = Counter(a)

    for count in number_count.values():
        if count > ceil(n/2):
            return 'NO'

    return 'YES'


if __name__ == '__main__':
    print(main())



