题目描述

不知道已经成为大学生的你是否还记得中位数这个东西，我们似乎很少再用到它，今天 $PK$ 就想让你做一下这个小学数学题。

初始你手里什么也没有，接下来 $PK$ 会按顺序给你 $n$ 个数。当你手中的数的个数为奇数时，你需要告诉 $PK$ 你手里这堆数的中位数是多少。

输入格式

第一行一个正整数 $n$ ，表示给你的数的个数。

接下来一行 $n$ 个整数，表示依次给你的这些数 $a_i$ 。

输出格式

输出 $x$ 行，每行一个整数，表示答案。

当 $n$ 为奇数时 $x = n/2 + 1$ ，当 $n$ 为偶数时 $x = n/2$ ，其中除法为下取整。

样例

样例输入1

5
1 2 3 4 5

样例输出1

1
2
3

样例输入2

6
4 9 1 2 7 -66666

样例输出2

4
4
4

数据范围与提示

$1 \le n \le 2 \cdot 10^5$

$|a_i| \le 10^9$

本题Idea来自2018年暑期集训期间与 $PK$ 的交流