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.
n=int(input())
a=list(map(int,input().split()))
if n==1:
    print("YES")
else:
    b=[]
    p=0
    b.append(a[0])
    i=1
    while i<n:
        if a[i]!=b[i-1]:
            b.append(a[i])
        else:
            if (i+1)<n:
                    a[i],a[i+1]=a[i+1],a[i]
                    if a[i]!=b[i-1]:
                        b.append(a[i])
                    else:
                        p=1
            else:
                p=1
        if p==1:
            break
        i+=1

    if p==1:
        print("NO")
    else:
        print("YES")