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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author shivam
 */
public class permutation {
    public static void main(String[]args) throws IOException
    {
        BufferedReader n=new BufferedReader(new InputStreamReader(System.in));
        int len=Integer.parseInt(n.readLine());
        
        int[] array=new int[1000];
        if(len==1)
        {
            System.out.println("YES");
        }
        else if(len==2)
        {
            StringTokenizer z=new StringTokenizer(n.readLine());
            if(Integer.parseInt(z.nextToken())==Integer.parseInt(z.nextToken()))
            {
                System.out.println("NO");
            }
        }
        else
        {   
            StringTokenizer o=new StringTokenizer(n.readLine());
            for(int i=0;i<len;i++)
            {
                int temp=Integer.parseInt(o.nextToken());
                array[temp-1]+=1;
                if(array[temp-1]>len/2+1)
                {
                    System.out.println("NO");
                    return;
                }
                else if(array[temp-1]>=len/2+1 && len%2==0)
                {
                    System.out.println("NO");
                    return;
                }
            }
            System.out.println("YES");
            
        }
    }
    
}
