Rearrange List Elements

Given a list of n integers, rearrange the list so that no two adjacent elements are equal. If it is not possible to rearrange, output an empty list ([]).

You are to implement an algorithm that checks whether the rearrangement is feasible and, if so, outputs one valid rearrangement. A necessary and sufficient condition for the existence of a rearranged sequence is that for each element, its frequency \( f \) satisfies \( f \leq \left\lfloor \frac{n+1}{2} \right\rfloor \). The algorithm should use a greedy approach (for example, using a priority queue) to choose the element with the highest remaining frequency while ensuring that it does not equal the previously placed element.

The input is provided via standard input and the result should be printed to standard output. The rearranged sequence should be printed as space-separated integers on a single line, or [] if no valid rearrangement exists.

inputFormat

The first line contains an integer n which denotes the number of elements in the list. The second line contains n space-separated integers representing the elements of the list.

outputFormat

If a valid rearrangement exists, output the rearranged list as space-separated integers on a single line. Otherwise, output [].

## sample

1
1

1

</p>