Problem H
Hot Springs
Kalle is visiting one of Iceland’s famous hot springs. It contains $n$ pools of water, where the $i$th one has temperature $t_ i$. Although staying in one of the warmer pools for a long time sure is relaxing, Kalle is on a very tight schedule and just wants a quick dip in each of the pools. As you may know, the nicest thing about hot baths is the contrast between hot and cold. Therefore, to get the most out of his stay, Kalle wants to find an ordering of the pools so that the difference in temperature between subsequent pools is increasing.
Given a sequence of pool temperatures $t_1, t_2, \dots , t_ n$, rearrange them into a new sequence $t’_1, t’_2, \dots , t’_ n$ such that for all $2 \leq i \leq n-1$ it holds that
\[ |t’_{i-1} - t’_ i| \leq |t’_ i - t’_{i+1}|. \]Input
The input consists of:
-
One line with an integer $n$ ($2 \le n \leq 10^5$), the number of pools.
-
One line with $n$ integers $t_1, \ldots , t_ n$ ($-10^5\leq t_ i \leq 10^5$ for each $i$), the temperatures in each of the $n$ pools.
Output
Output a rearrangement of the sequence satisfying the given requirement. If no solution exists, output “impossible”. If there are multiple valid solutions, you may output any one of them.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 3 4 |
4 3 1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 0 0 1 -1 -6 3 |
0 1 3 -1 -6 0 |
