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.
The first line contains integer *n* (1 ≤ *n* ≤ 100) — the number of elements in the array. The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 1000) — the array elements.
import sys
import heapq
from collections import Counter

def main(arr):
    counts = list(map(lambda x: -x, Counter(arr).values()))
    heapq.heapify(counts)
    while counts:
        curr = heapq.heappop(counts)
        if curr == -1:
            print("YES")
            return
        
        if not counts:
            # Need to solve the current one
            # but can't.
            print("NO")
            return

        n = heapq.heappop(counts)
        curr, n = abs(curr), abs(n)
        if n == curr:
            # Interleave them, we've solved both.
            continue
        elif n > curr:
            # Use curr to satisfy n.
            heapq.heappush(counts, curr - n)
        elif n < curr:
            heapq.heappush(counts, n - curr)

if __name__ == "__main__":
    arr = []
    for e, line in enumerate(sys.stdin.readlines()):
        if e == 0:
            continue
        arr = list(map(int, line.strip().split()))
    main(arr)
