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.
import java.util.*;
public class Yaroslav296A {
    
    public static int[] swap(int []numbers, int index1, int index2){
//      int k=0;
//      int j=0;
//      k=numbers[index1];
//      j=numbers[index2];
//      numbers[index2]=k;
//      numbers[index1]=j;
        
        int k=0;
        k=numbers[index1];
        numbers[index1]=numbers[index2];
        numbers[index2]=k;
        
        return numbers;
    }
    //Creates an array where each index represents the number of occurrences of a number. If there are negative numbers, it is shifted to the right by the value of the negative number.
    public static int [] countOccurrences(int [] numbers){
        Arrays.sort(numbers);
        int min=numbers[0];
        int max=numbers[numbers.length-1];
        
        int occurrenceLength=0;
        if(min<0){
            occurrenceLength=max-min;
        }
        else{
            occurrenceLength=max;
        }
        int [] occurrences=new int[occurrenceLength+1];
        for(int i=0;i<numbers.length;i++){
            occurrences[numbers[i]]++;
        }
        
        return occurrences;
        
        
    }
    

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
    
        Scanner in=new Scanner(System.in);
    
    int n=in.nextInt();
        int [] numbers=new int[n];
        for(int i=0;i<n;i++){
            numbers[i]=in.nextInt();
        }
        
        int []occurrences=countOccurrences(numbers);
        Arrays.sort(occurrences);
        if(occurrences[occurrences.length-1]>Math.ceil(numbers.length/2.0))
            System.out.print("NO");
        else
            System.out.println("YES");
        
        
        
        
        }
        
        
    }


