逝去的过往,就别再回头望,逝去的过往.
---迷途羔羊

题目背景

在数据分析和算法领域，中位数是一个非常重要的统计指标，能够反映一个数据集的中心趋势。它在应对极端值（outliers）时表现出色，不像平均值那样容易受到影响。在实际应用中，例如金融分析、医学研究和质量控制等场景，常常需要动态计算数据流的中位数，尤其是当新数据不断到达时。

这次的任务是基于一个增长的序列，计算前若干奇数项的中位数。想象一个实时监控系统，它接收一连串的非负整数数据，系统需要在每次收到奇数项后，立即计算并输出中位数，以便作出快速反应和调整。这个问题的核心是如何在高效的时间内找到动态数据流的中位数，尤其是在数据量非常大的情况下。

题目描述

给定一个长度为 $N$ 的非负整数序列 $A$，每次加入一个奇数项后计算并输出当前奇数项的中位数。

输入格式

第一行包含一个正整数 $N$，表示序列的长度。

第二行包含 $N$ 个非负整数 $A_{1}, A_{2}, \dots, A_{N}$，表示序列中的元素。

输出格式

输出 $\lfloor \frac{N + 1}{2} \rfloor$ 行。第 $i$ 行输出序列 $A_{1}, A_{2}, \dots, A_{2i-1}$ 的中位数。

样例 #1

样例输入 #1

7
1 3 5 7 9 11 6

样例输出 #1

1
3
5
7

样例 #2

样例输入 #2

7
3 1 5 9 8 7 6

样例输出 #2

3
3
5
6

提示

对于 $20\%$ 的数据，$N \le 100$；

对于 $40\%$ 的数据，$N \le 3000$；

对于 $100\%$ 的数据，$1 \le N \le 10^7$，$0 \le A_i \le 10^9$。