P17033 [NWERC 2020] 温泉 / Hot Springs

译自 [Northwestern Europe Regional Contest (NWERC) 2020](http://2020.nwerc.eu)。

冰岛以地热活动闻名，这为该国提供了大量电力和供暖。地热也以温泉的形式，成为人们享受的来源。 Kalle 正在游览冰岛著名的温泉之一。这个温泉包含 $n$ 个水池，其中第 $i$ 个水池的温度为 $t_i$。虽然长时间待在较暖的水池里确实很放松，但 Kalle 的日程非常紧张，他只是想在每个水池里快速泡一下。你也许知道，热水浴最美妙的地方在于冷热之间的对比。因此，为了尽可能充分享受这次停留，Kalle 想找出一个游览水池的顺序，使得相邻水池之间的温度差逐渐增大。 给定水池温度序列 $t_1,t_2,\ldots,t_n$，请将它们重新排列成一个新序列 $t'_1,t'_2,\ldots,t'_n$，使得对于所有 $2 \le i \le n-1$，都有 $$ |t'_{i-1}-t'_i| \le |t'_i-t'_{i+1}|. $$

输入包括： - 第一行包含一个整数 $n$（$2 \le n \le 10^5$），表示水池数量。 - 第二行包含 $n$ 个整数 $t_1,\ldots,t_n$（对每个 $i$，有 $-10^5 \le t_i \le 10^5$），表示这 $n$ 个水池的温度。

输出一个满足要求的重排序列。如果不存在解，输出 `impossible`。如果存在多个合法解，你可以输出任意一个。

【数据规模与约定】 - $2 \le n \le 10^5$。 - $-10^5 \le t_i \le 10^5$。 - 若有多个合法重排，可以输出任意一个。