A. Yaroslav and Permutations

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 a₁, a₂, ..., a_n (1 ≤ a_i ≤ 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.

Sample test(s)

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.

 这是一道很简单的题。。。不过注意题目的理解：元素是可以交换多次的。分n为奇数和偶数两种情况讨论即可。

1 #include 
        
          2 #include 
         
           3 #include 
          
            4 #include 
           
             5 #include 
            
              6 using namespace std; 7  8 int main() 9 {10     int n, a[101], cnt[1001];11     bool ok;12     while(scanf("%d", &n) != EOF)13     {14         ok = true;15         memset(cnt, 0, sizeof(cnt));16         for(int i = 0; i < n; i++)17         {18             scanf("%d", &a[i]);19             cnt[a[i]]++;20         }21         int max = 0;22         for(int i = 1; i < 1001; i++)23             if(max < cnt[i]) max = cnt[i];24         if((n & 1) && (max > n / 2 + 1)) ok = false;25         else if(!(n & 1) && (max > n / 2)) ok = false;26         if(ok) cout << "YES\n";27         else cout << "NO\n";28     }29     return 0;30 }