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.Arrays;
import java.util.Scanner;

public class permutation {
	public static void main(String[] args) {
	Scanner a = new Scanner(System.in);
	 int n = a.nextInt();
	 int arr [] = new int [n];
	 arr[0] = a.nextInt();
	 int i = 0;
	 int one = 0;
	 int two = 0;
	 for(int y = 1 ; y < n ;y++) {
		 arr[y] = a.nextInt();
	 }
	Arrays.sort(arr);
	int ii = 0;
	int maxno =0;
	if(n != 1) {
	while(ii < n) {
		if(ii+1 < n) {
	  if (arr[ii] == arr[ii+1]) {
		  //System.out.println(arr[ii]+"     "+arr[ii+1]);
		  maxno++;
	  }else {
		  break;
	  }
	  
		}
		ii++;
	}
	maxno++;
	//System.out.println(maxno+"      first");
	int maxapp = 1;
	for(int j = maxno ;j <n; j++ ) {
		//System.out.println(j+"    "+n);
		if(j+1 < n) {
			//System.out.println("*****");
		if(arr[j] == arr[j+1]) {
			//System.out.println(arr[j]+"       "+arr[j+1]);
			maxapp++;
		}else {
			maxapp = 0;
		}
		}
		if(maxapp > maxno) {
			maxno = maxapp;
		}		
	}
	//System.out.println(maxno+"      second");
	 int diff = n - maxno;
	// System.out.println(maxno+"   "+diff);
	 if(diff >= maxno-1) {
		 System.out.println("YES");
	 }else {
		 System.out.println("NO");
	 }
	}else {
		System.out.println("YES");
	}
	 
	 
	 
	 
	}
	

	
}
