题目描述

中位数是按顺序排列的一组数据中居于中间位置的数。

现在依次给你 $n$ 个数 $a_1,a_2,…,a_n$ (保证 $n$ 为奇数)，你需要给出读入到第 $1,3,5,…,n$ 个数时，当前的中位数是多少。

输入格式

第一行一个整数 $n$。

接下来一行共 $n$ 个数。

输出格式

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

9
1 2 3 4 5 6 7 8 9

1 2 3 4 5

数据规模

对于100%的数据，保证$1≤n≤10^5,1≤a_i≤10^9$。