Rearrange List to Avoid Adjacent Duplicates

You are given a list of integers. Your task is to rearrange the integers in the list such that no two adjacent integers are the same. If such a rearrangement is not possible, output an empty list.

More formally, given an array \(a_1, a_2, \ldots, a_n\), reorder it to obtain \(b_1, b_2, \ldots, b_n\) such that for all \(1 \leq i < n\), \(b_i \neq b_{i+1}\). If no valid rearrangement exists, output [].

It is guaranteed that when a valid rearrangement exists, any valid rearrangement will be accepted.

inputFormat

The first line of input contains an integer \(n\) denoting the number of elements in the list. The second line contains \(n\) space-separated integers.

For example:

4
1 2 1 2

outputFormat

If a valid rearrangement exists, output a single line containing the rearranged list as space-separated integers. If no valid rearrangement exists, output [] (without quotes).

## sample

1
1

1

</p>