g5-08232. 中位数流 未做

数据流里依次到来 $n$ 个整数。每读入一个，输出当前已读入所有数的中位数：把已读的数从小到大排好，取第 $\lfloor (m+1)/2\rfloor$ 个（$m$ 为当前个数，位置从 $1$ 数起）——奇数个时是正中间，偶数个时是中间两个里较小的那个。

双堆技法：用一个大根堆装较小的一半、一个小根堆装较大的一半，两堆元素个数始终满足「左堆等于右堆，或恰好多 $1$」。中位数就是左堆的堆顶。

第一行一个整数 $n$（$1\le n\le 2\times 10^5$）。

第二行 $n$ 个整数 $a_i$（$-10^9\le a_i\le 10^9$），依次到来。

共 $n$ 行，第 $i$ 行一个整数：读入前 $i$ 个数后的中位数。

输入：

4
5 1 4 2

输出：

5
1
4
2

读入 4 个数后排序为 1 2 4 5，中间偏小的是 2；逐步答案见样例。

$1\le n\le 2\times 10^5$，$-10^9\le a_i\le 10^9$。提示：偶数个时答案是左堆堆顶（较小中位）——取到右堆堆顶就是取了较大的那个，偶数步的答案会整体偏大。