Reorder Students by Height

You are given a list of integers representing the heights of students. Your task is to rearrange the list such that no two adjacent students have the same height. If it is impossible to produce such an ordering, output an empty line.

The problem can be modeled using a greedy algorithm. One common approach is to use a max‐heap (priority queue) to always pick the number with the highest remaining frequency and then update its count. Care must be taken to avoid placing the same element consecutively.

Note: If the rearrangement is possible, output any valid ordering that meets the criteria.

inputFormat

The input is given via standard input (stdin) and has the following format:

n
h1 h2 ... hn

Here, n is the number of students, and h1, h2, ..., hn are the space-separated integers representing the heights of the students.

outputFormat

Output via standard output (stdout) a single line containing the rearranged heights separated by a space such that no two adjacent heights are the same. If no valid rearrangement exists, output an empty line.

6
1 1 2 2 3 3

1 2 3 1 2 3