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.
# python 3
"""
Note that after applying the operations of the exchange, we can get any permutation of the elements of the array.
It is not difficult to understand that the answer would be "YES" if there were at least another different
number between the same-valued number, and this means that at most the same-valued number would appear
(n+1)/2 times. Thus, if the most seen number appear C times, it must fulfill the condition C <= (n+1) / 2.
"""


def yaroslav_and_permutations(n_int: int, numbers_list: list) -> str:
    times = dict()
    for each in numbers_list:
        if times.get(each, -1) == -1:
            times[each] = 1
        else:
            times[each] += 1
    max_seen = 0
    for (number, seen_time) in times.items():
        if seen_time > max_seen:
            max_seen = seen_time
    if max_seen <= (n_int + 1) // 2:
        return "YES"
    else:
        return "NO"


if __name__ == "__main__":
    """
    Inside of this is the test. 
    Outside is the API
    """
    n = int(input())
    numbers = list(map(int, input().split()))
    print(yaroslav_and_permutations(n, numbers))
