Rearrange Array to Avoid Adjacent Duplicates

You are given an array of n integers. The task is to rearrange the elements of the array such that no two adjacent elements are equal. If such a rearrangement is possible, output any valid rearrangement; otherwise, output an empty array represented by [].

The difficulty of this problem lies in ensuring that the arrangement meets the condition of non-equality for every adjacent pair. A common strategy is to count the frequency of each number and then place the most frequent numbers in alternate positions. This method can be expressed by the condition that for a valid rearrangement, the maximum frequency must not exceed \(\lceil n/2 \rceil\). Specifically, if \(\max(\text{frequency}) > \frac{n+1}{2}\), then no valid arrangement exists.

Note: The output must be produced using standard input and output.

inputFormat

The input consists of two lines:

• The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), representing the number of elements in the array.
• The second line contains \(n\) space-separated integers \(a_i\) (\(1 \le a_i \le 10^9\)).

outputFormat

If a valid rearrangement exists, print the rearranged array as \(n\) space-separated integers on one line. If no valid rearrangement exists, print [] (without quotes).

6
1 1 2 2 3 3

1 2 1 3 2 3