黑龙每秒钟喷出的火球的直径都不相同，一共喷出了n个火球。为了更好地抵挡住火球，黑龙每喷出第i团火球之后，需要知道当前所有的i个火球从小到大排序后，排在第i/2个的火球直径，如果只有一个火球就输出这个火球的直径。

输入:
第一行一个整数n。(n<=100000)

第二行n个整数，每一行都代表一次黑龙喷出的火球直径。(火球直径<=100)

输出:
共n行，每行一个数，第i行的数表示黑龙喷出第i团火球后，直径大小排在第i/2个的火球的直径。

输入样例1:
5
3 1 3 2 3

输出样例1:
3
1
1
2
2

输入样例2:
5 2 3 4 5 9

输出样例2:
2
2
2
3
3

用时/内存:
1000MS/256MB