题目描述

FJ正在调查他的牛群，以找到最具代表性（平均水平）的奶牛。他想知道这头“中位数”奶牛的产奶量是多少：即有一半的奶牛产奶量大于或等于中位数，另一半奶牛产奶量小于或等于中位数。 给定奇数头奶牛的数量N (1 <= N < 10,000)以及它们各自的产奶量（( 1 ) 到 ( 1,000,000 )），找出中位数的产奶量，使得至少一半的奶牛产奶量与此相同或更多，且至少一半的奶牛产奶量与此相同或更少。

输入

第 ( 1 ) 行：一个整数 ( N )

第 ( 2 ) 行到 ( N + 1 ) 行：每行包含一个整数，表示一头奶牛的产奶量。

输出

第 ( 1 ) 行：一个整数，表示中位数的产奶量。

5
2
4
1
3
5

3

提示

输入细节： 五头奶牛，产奶量分别为 ( 1 ) 到 ( 5 ) 输出细节： ( 1 ) 和 ( 2 ) 小于 ( 3 )；( 4 ) 和 ( 5 ) 大于 ( 3 )。

来源

USACO 2004 November