Hamako Online Judge

TLE
2sec

MLE
128MB

得点
400

問題

あなたは空の配列 $A$ に対して $N$ 個の整数を $1$ 番目から順番に追加していく。
$i$ $(1 \leq i \leq N)$ 個目の整数 $a_i$ を $A$ に追加したときの $A$ の中央値を出力せよ。
中央値が小数となる場合は小数点以下切り捨てとし、整数で出力せよ。

入力は以下の形式で標準入力から与えられる。

$N$
$a_1$ $a_2$ $\ldots$ $a_N$

出力は $N$ 行からなる。
$i$ 個目の整数 $a_i$ を $A$ に追加したときの $A$ の中央値を改行区切りで出力せよ。
中央値が小数となる場合は小数点以下切り捨てとし、整数で出力せよ。
出力の末尾には改行を入れること。

5
9 3 8 1 0

$(i = 1)$ $A=\{9\}$ となり、$A$ の中央値は $9$ となる。
$(i = 2)$ $A=\{3,9\}$ となり、$A$ の中央値は $\frac{3+9}{2} = 6$ となる。
$(i = 3)$ $A=\{3,8,9\}$ となり、$A$ の中央値は $8$ となる。
$(i = 4)$ $A=\{1,3,8,9\}$ となり、$A$ の中央値は $\frac{3+8}{2} = 5.5$ となるため、小数点以下を切り捨て、$5$ となる。
$(i = 5)$ $A=\{0,1,3,8,9\}$ となり、$A$ の中央値は $3$ となる。

4
1 9 0 3

20
44 289 37 250 6 208 16 77 13 284 22 472 39 147 22 229 34 422 50 29