Rearrange Trees

John is an avid gardener who wants to plant trees in a single row. He has a sequence of trees represented by integers. His goal is to rearrange the trees such that no two trees of the same type are adjacent. Formally, if the rearranged sequence is \(a_1, a_2, \dots, a_N\), then for every \(1 \leq i < N\) we require \(a_i \neq a_{i+1}\). A necessary condition for a valid rearrangement is that for each tree type with frequency \(f\), it must hold that \(f \leq \lceil N/2 \rceil\). If it is impossible to achieve such a sequence, output an empty list.

Input Format: The first line contains an integer \(N\) representing the number of trees. The second line contains \(N\) space-separated integers representing the types of trees.

Output Format: Output a single line. If a valid rearrangement exists, print the rearranged sequence as space-separated integers. Otherwise, print [] (without quotes).

inputFormat

The first line contains an integer \(N\) (\(0 \leq N \leq 10^5\)). The second line contains \(N\) integers (each representing a tree type) separated by spaces.

outputFormat

If a valid rearrangement exists such that no two adjacent trees are of the same type, output the rearranged list as space-separated integers on one line. If no valid rearrangement exists, print [].

6
3 3 3 2 2 1

3 2 3 1 2 3