UOJ Logo Universal Online Judge

UOJ

统计

最终吉米多出题斯基没有找到优质的题目,于是高产的吉米多出题斯基决定自己出一道。

首先,吉米多出题斯基脑洞了一道难度为 $h_1$ 的题目,然而吉米多出题斯基觉得太水了,于是把这题稍微改了改变成了一道难度为 $h_2$ 的。然而吉米多出题斯基还是觉得太水了,又稍微改了改变成了难度为 $h_3$ 的。如此进行下去吉米多出题斯基脑洞出了 $n$ 个版本的题目,难度分别为 $h_1, \dots, h_n$。

由于吉米多出题斯基在脑洞的时候只是随便改了改题目条件,所以每次改题并不一定会变难。但神奇的是,每次产生一个新版本的题目后,吉米多出题斯基手上所有版本的题目难度的中位数不会降低。

很快吉米多出题斯基出好了题,造好了 UOI,选手们纷纷阵亡。多年后吉米多出题斯基再看到自己曾经出的这道题时感叹道:“都是回忆啊……”

可是吉米多出题斯基突然发现自己只记得脑洞过程产生的 $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 m / 2 \rceil$ 的数;若 $m$ 为偶数则定义中位数为从小到大第 $m/2$ 和第 $m/2+1$ 的数的平均值。

输入格式

第一行一个正整数 $n$。

接下来一行 $n$ 个整数 $a_1, \dots, a_n$。

输出格式

一行,$n$ 个整数表示你找到的字典序最大的 $h_1, \dots, h_n$。

如果无解,输出卖萌表情 "QwQ"。

样例一

input

5
1 2 3 4 5

output

1 3 2 5 4

explanation

中位数依次为:$\{1, 2, 2, 2.5, 3\}$。

样例二

input

8
1 2 2 3 3 3 4 4

output

3 3 4 3 4 2 2 1

样例三

见样例数据下载。

限制与约定

子任务 分值 $n$ 其他约定
110$1 \leq n \leq 10$
210$1 \leq n \leq 100$
320$1 \leq n \leq 2000$
430$1 \leq n \leq 10^5$$a_i$ 互不相同
530$1 \leq n \leq 10^5$

对于所有数据,满足 $1 \le a_i \le 10^9$。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载