Reorder Array to Avoid Adjacent Duplicates

Given an array of n integers, determine if it is possible to rearrange the array so that no two adjacent elements are equal. More formally, let ( n ) be the number of elements in the array and let the frequency of any element be denoted by ( f ). A valid reordering is possible if and only if:

[ \max_{x} f(x) \leq \left\lceil \frac{n}{2} \right\rceil ]

where ( \left\lceil \cdot \right\rceil ) represents the ceiling function. The program should output "YES" if such a reordering exists, and "NO" otherwise.

inputFormat

The first line of input is an integer ( n ) representing the number of elements in the array. The second line contains ( n ) space-separated integers.

outputFormat

Output a single line containing "YES" if it is possible to rearrange the array such that no two adjacent elements are equal, or "NO" otherwise.## sample

6
1 1 2 3 3 4

YES