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.
'''
Created on Apr 6, 2013

@author: Nagatobimaru
'''
from __future__ import division;
from bisect import *;
from fractions import Fraction;
import sys;
import math;
import io;

INF = 987654321987654321987654321;

def readint(delimiter=' ') :
    return map(int, raw_input().split(delimiter));

def readstr() :
    return raw_input().split();

def readfloat() :
    return map(float, raw_input().split());

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i - 1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i - 1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError


def bin_search(a, x, left, right) :

    while left <= right :
        mid = (left + right) // 2;
        
        if a[mid] == x :
            return mid;
        elif a[mid] < x :
            left = mid + 1; 
        elif a[mid] > x :
            right = mid - 1;
                       
        pass
    
    return -1;
    pass

if __name__ == '__main__':
    
    n = input();
    hmap = {};
    
    for ii in readint() :
        if ii not in hmap :
            hmap[ii] = 1;
        else :
            hmap[ii] += 1;
            
    maxfreq = 0;
    
    for ii in hmap.keys() :
        maxfreq = max(maxfreq, hmap[ii]);
    
    if maxfreq > math.ceil(n / 2) :
        print "NO";
    else :
        print "YES";
    
    
    
    pass

