题目描述

中位数是按顺序排列的一组数据中居于中间位置的数。 现在依次给你 n 个数ai(n为奇数)。你需要给出读入到第1,3,5,…,n个数时，当前的中位数是多少。

输入格式

第一行一个数n，接下来一行n个数。

输出格式

一行，输出(n+1)/2个数，表示答案。

样例

输入样例 1

9
1 2 3 4 5 6 7 8 9

输出样例 1

1 2 3 4 5

输入样例 2

1
0

输出样例 2

0

输入样例 3

3
1 2 3

输出样例 3

1 2

提示

数据范围：1≤n≤100000 的奇数,1≤ai≤2^31。 【对于这道题，我们可以维护一个小根堆，和一个大根堆，让大根堆中的最大值小于小根堆的最小值，并且大根堆的元素个数比小根堆大1，这样大根堆的堆顶一直都是中位数】 题目来源：OJ题库 题目ID:T1756