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 java.io.IOException;
import java.util.Scanner;
import java.util.Vector;

public class Main { 
    //A. Yaroslav and Permutations
    public static String checkArray(int arr[])
    {
        int count[] = new int[1000];

        for (int i = 0; i < arr.length; i++)
            count[arr[i]]++;

        for (int i = 0; i < 1000; i++)
            if(count[i] > Math.ceil(arr.length/2) + 1)
                return "NO";
        return "YES";

    }
    
    public static void main(String[] args) throws IOException {
        int n;
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        int arr[] = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = input.nextInt();
        System.out.println(checkArray(arr));

    }
}