296A.md (1207B)
1 Source: https://codeforces.com/problemset/problem/296/A 2 3 A. Yaroslav and Permutations 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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. 22 23 Help Yaroslav. 24 25 Input 26 27 The first line contains integer *n* (1 ≤ *n* ≤ 100) — the number of elements in the array. The second line contains *n* integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 1000) — the array elements. 28 29 Output 30 31 In the single line print "YES" (without the quotes) if Yaroslav can obtain the array he needs, and "NO" (without the quotes) otherwise. 32 33 Examples 34 35 Input 36 37 ``` 38 1 39 1 40 ``` 41 42 Output 43 44 ``` 45 YES 46 ``` 47 48 Input 49 50 ``` 51 3 52 1 1 2 53 ``` 54 55 Output 56 57 ``` 58 YES 59 ``` 60 61 Input 62 63 ``` 64 4 65 7 7 7 7 66 ``` 67 68 Output 69 70 ``` 71 NO 72 ``` 73 74 Note 75 76 In the first sample the initial array fits well. 77 78 In the second sample Yaroslav can get array: 1, 2, 1. He can swap the last and the second last elements to obtain it. 79 80 In the third sample Yarosav can't get the array he needs.