[Usaco2005 qua]Who's in the Middle

FJ 正在调查牛群，希望找出产奶量最接近平均水平的奶牛。他将这头奶牛的产奶量定义为牛群产奶量的中位数：至少一半的奶牛产奶量不小于它，同时至少一半的奶牛产奶量不大于它。

给定奇数头奶牛及每头奶牛的产奶量，请将所有产奶量按升序排列，并求出位于中间位置的产奶量。

输入格式

第一行输入一个奇数 $N$，表示奶牛的数量。

接下来 $N$ 行，每行输入一个整数，表示一头奶牛的产奶量。

输出格式

输出一个整数，表示所有奶牛产奶量的中位数。

样例输入

5
2
4
1
3
5

样例输出

3

数据范围

• $1\le N<10^4$，且 $N$ 为奇数；
• 每头奶牛的产奶量均为 $1$ 到 $10^6$ 之间的整数。

来源与许可

本题为 USACO 2005 试题「Who's in the Middle」，题面与测试数据整理自 BZOJ。

样例 1

输入

5
2
4
1
3
5

输出

3