UOJ Logo Universal Online Judge

UOJ

附件下载 统计

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

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

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

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

可是吉米多出题斯基突然发现自己只记得脑洞过程产生的 n 个版本难度是 a1,,an,却不记得每个 ai 对应的是第几个版本了。

吉米多出题斯基日理万机没有时间再细想了,于是他找到了你 —— 风璃殇做不出题耶维奇,请你帮助吉米多出题斯基把 a1,,an 排列顺序,给出一组满足条件且字典序最大的 h1,,hn 吧!

对于一个数列 v1,,vm,若 m 为奇数则定义中位数为从小到大第 m/2 的数;若 m 为偶数则定义中位数为从小到大第 m/2 和第 m/2+1 的数的平均值。

输入格式

第一行一个正整数 n

接下来一行 n 个整数 a1,,an

输出格式

一行,n 个整数表示你找到的字典序最大的 h1,,hn

如果无解,输出卖萌表情 "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 其他约定
1101n10
2101n100
3201n2000
4301n105ai 互不相同
5301n105

对于所有数据,满足 1ai109

时间限制:1s

空间限制:256MB

下载

样例数据下载