Cossack Vus and Lexicography#10358
Kozak recently received an array consisting of integers.
Vus wants to rearrange the elements of this array so that no two adjacent numbers are the same. Among all possible arrangements, he is interested in finding the lexicographically smallest one.
To clarify, lexicographical order is determined as follows: Given two arrays, identify the first position where they differ. If the element in the first array is smaller at this position, then the first array is considered lexicographically smaller. Conversely, if the element in the second array is smaller, then the first array is larger. For example, the following inequalities hold: [10, 3, 1] < [10, 4, 5], [1, 1, 1] < [1, 2, 3], and [1, 2, 3] < [10, 10, 10].
The first line contains an integer (1 \leq n \leq 5 \cdot 10^5), representing the number of elements in the array.
The second line contains integers a_1, a_2, \ldots, a_n (1 \leq a_i \leq 5 \cdot 10^5), which are the elements of the array.
If it is impossible to rearrange Vus's array to meet the conditions, output a single number .
Otherwise, output integers representing the lexicographically smallest arrangement of Vus's array.
Example 1
Example 2
Example 3
In the first example, there is only one possible arrangement.
In the second example, other arrangements exist, such as [1, 2, 3, 4, 1, 2] or [1, 4, 1, 2, 3, 2]. However, all these arrangements are lexicographically larger than [1, 2, 1, 2, 3, 4].
In the third example, no valid arrangement exists because the array will always have two adjacent ones.
This problem uses post-test scoring with the following additional constraints:
( points): n \leq 10^3, a_i \leq 2
( points): n \leq 10^3, a_i \leq 3
( points): n \leq 10^3, a_i \leq 5 \cdot 10^5
( points): n \leq 5 \cdot 10^5, a_i \leq 2
( points): n \leq 5 \cdot 10^5, a_i \leq 3
( points): n \leq 5 \cdot 10^5, a_i \leq 5 \cdot 10^5