You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

“取舍”是cqupt风华军爷，他认识的老登总是散布谣言说高数挂科率会高达50%，吓的取舍不得不在站军姿的同时还在脑补宋浩老师的恋爱小故事（因为取舍只记得他讲的恋爱小故事）。

因为取舍恋爱故事听多了，所以他希望自己是一个受同学欢迎的邮兵，我们定义：每个人都有一个魅力值，假如取舍的魅力值比自己所在连队（除自己外）一半的人都要高(向上取整),那么我们可以认为取舍是受同学欢迎的邮兵。

Input Format

第一行输入一个整数$n$($2 \le n \le 10^6$)表示取舍所在连队除了自己以外的总人数。

第二行输入$n$个数，分别是$a_1$,$a_2$,$a_i$...$a_n$($0 \le a_i \le 10^9$)表示第i个人的魅力值。

Output Format

输出一个数ans，表示取舍最少需要拥有多少魅力值，才能成为一个受同学欢迎的邮兵？

Sample

输入 #1

6
3 4 5 5 6 7

输出 #1

6

Hint

向上取整的符号为：$\left \lceil x \right \rceil$，向上取整的定义为：$\left \lceil x \right \rceil= min \{n \in Z \; |x \le n \}$.

对$x$向上取整的结果，表示为不小于$x$的最小整数，例如：

$\left \lceil 4 \right \rceil = 4$,$\left \lceil 4.001 \right \rceil = 5$,$\left \lceil 2.5 \right \rceil = 3$