Rearrange Array to Avoid Adjacent Duplicates

You are given an array of integers. Your task is to determine whether it is possible to rearrange the elements of the array such that no two adjacent elements are the same.

Explanation: Let \( n \) be the number of elements in the array. Define \( f(x) \) as the frequency of an element \( x \). In order for a valid rearrangement to exist, the following condition must be met:

[ \max_{x} f(x) \leq \frac{n+1}{2} ]

If the above condition holds, output Yes; otherwise, output No. In the case of an empty array, output No.

inputFormat

The input is given via standard input (stdin) and consists of two parts:

• The first line contains an integer \( n \) denoting the number of elements in the array. If \( n = 0 \), the array is empty.
• If \( n > 0 \), the second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

Output a single line via standard output (stdout) that contains either Yes if it is possible to rearrange the elements so that no two adjacent elements are the same, or No otherwise.

6
1 1 1 2 2 3

Yes