s09204. 中位数柜台 · 林老师的题库

题目描述

一名柜员依次登记 $n$ 个数值。中位数口径规定如下：已登记个数 $c$ 为奇数时，中位数是正中间的那个； $c$ 为偶数时，取中间两个数中较小的一侧（靠左）为中位数。

每登记完一个数值，柜台就要报出当前已登记全部数值的中位数，共报 $n$ 次。

第一行一个整数 $n$ 。

第二行 $n$ 个整数 $a_{1}, a_{2}, \dots, a_{n}$ ，按登记顺序给出。

共 $n$ 行，第 $i$ 行输出登记完 $a_{i}$ 后的中位数。

输入

3
3 1 4

输出

3
1
3

三个时刻的已登记集合依次为 ${3}$ 、 ${1, 3}$ 、 ${1, 3, 4}$ ：第一个正中间为 $3$ ；第二个取较小一侧得 $1$ ；第三个正中间为 $3$ 。