3875: zzh冠李戴
内存限制：256 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：235
解决：45
题目描述
zzh总共有n顶帽子，每顶帽子有自己的一个编号。在第0天时所有帽子都收拾好在柜子里，每一天开始的时候，zzh会从柜子里取出一顶帽子，然后他会把已经取出的所有帽子按编号大小排序，假设现在是第i天，他就会把排好序后的第(i+1)/2顶帽子戴在头上。现在他想知道从第1天到第n天的每一天，他戴的帽子的编号是多少。
这里的(i+1)/2指的是(i+1)/2向下取整，例如(1+4)/2=2,(1+6)/2=3等......
这里的(i+1)/2指的是(i+1)/2向下取整，例如(1+4)/2=2,(1+6)/2=3等......
输入
单组数据
第一行为一个整数n，表示zzh总共有n顶帽子 （1<=n<=1e6）
接下来的n行，每行一个整数，为zzh当天取出的帽子编号ai（ -1e18<=ai<=1e18）
因为有可能某些帽子是在同一家店买的，所以编号有可能相同。
第一行为一个整数n，表示zzh总共有n顶帽子 （1<=n<=1e6）
接下来的n行，每行一个整数，为zzh当天取出的帽子编号ai（ -1e18<=ai<=1e18）
因为有可能某些帽子是在同一家店买的，所以编号有可能相同。
输出
输出n行，每行一个整数，即zzh当天戴的帽子的编号。
样例输入 复制
4
1
1
1
2
样例输出 复制
1
1
1
1