Rearranging Students by Height

Given a list of student heights, rearrange them so that no two adjacent students have the same height. It is guaranteed that a valid rearrangement exists. You can think of it similar to the task of rearranging letters in a string so that no two adjacent letters are identical. In particular, if we denote the frequency of a height by (f) and the total number of students by (n), then a necessary condition for a solution is that (\max(f) \leq \left\lceil\frac{n}{2}\right\rceil).

For example, if the input heights are [5, 5, 5, 6, 6, 6], one valid output is [5, 6, 5, 6, 5, 6].

inputFormat

The first line contains a single integer (n) representing the number of students. The second line contains (n) integers separated by spaces, where each integer represents the height of a student.

outputFormat

Output a single line containing the rearranged sequence of (n) integers, separated by spaces, such that no two adjacent integers are the same.## sample

6
5 5 5 6 6 6

5 6 5 6 5 6