Description

中位数（Median）：
统计学名词，是指将统计总体当中的各个变量值按大小顺序排列起来，形成一个数列，处于变量数列中间位置的变量值就称为中位数，用Me表示。当变量值的项数N为奇数时，处于中间位置的变量值即为中位数；当N为偶数时，中位数则为处于中间位置的2个变量值的平均数。（摘自百度百科）

现在给你一个空数组，然后依次往里面插入N个数字。请在每次插入一个数字之后输出当前数组的中位数。

Input

第一行一个整数N，表示要插入的数字个数。(1<=N<=100,000)
第二行N个整数num[1]~num[N]，按序依次表示每次插入的数字。（-100,000<=num[i]<=100,000,num[i] mod 2 = 0）

Output

N行，每行一个整数，表示每次插入一个数字之后当前数组的中位数。

Sample Input

5
2 4 6 8 10

Sample Output

2
3
4
5
6

HINT

Source

NBU OJ