### 问题描述 康康出了 $n$ 个版本的题目，难度分别为 $h_1, \dots, h_n$。由于康康只是随便改了改题目条件，所以每次改题并不一定会变难。但神奇的是，每次产生一个新版本的题目后，康康手上所有版本的题目难度的中位数不会降低。 康康有点健忘，所以只记得产生的 $n$ 个版本难度是 $a_1, \dots, a_n$，却不记得每个 $a_i$ 对应的是第几个版本了。 现在他想请你帮助他把 $a_1, \dots, a_n$ 排列顺序，给出一组满足条件且字典序最大的 $h_1, \dots, h_n$。 对于一个数列 $v_1, \dots, v_m$，若 $m$ 为奇数则定义中位数为从小到大第 $\lceil \frac{m}{2} \rceil$ 的数；若 $m$ 为偶数则定义中位数为从小到大第 $\frac{m}{2}$ 和第 $\frac{m}{2}+1$ 的数的平均值。 ### 输入格式 第一行一个正整数 $n$。 接下来一行 $n$ 个整数 $a_1, \dots, a_n$。 ### 输出格式 一行，$n$ 个整数表示你找到的字典序最大的 $h_1, \dots, h_n$。 如果无解，输出 `QwQ`。 ### 样例输入 ``` 5 1 2 3 4 5 ``` ### 样例输出 ``` 1 3 2 5 4 ``` ### 评测数据规模 $1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^9$。