题目描述

JOI 高校的一年级共有 $N$ 人，并被编号为从 $1$ 到 $N$。

某天，一年级的 $N$ 人参加了考试。学生 $i$（$1 \le i \le N$）的得分为 $A_i$ 分。这里，$N$ 人并不是都取得了相同的分数。

根据这次考试的成绩来决定明年的分班。具体来说，选择一个整数 $x$，将 $N$ 名学生分成两个班：得分在 $x$ 分以上（含 $x$ 分）的学生进入升学班，得分低于 $x$ 分的学生进入普通班。

在此，要求每个班都至少有 $1$ 名学生，并且选择一种分法，使升学班的人数与普通班的人数之差最小。进一步地，如果满足条件的分法有多个，则在其中选择升学班人数最少的分法。

给定学生人数以及每位学生的得分，编写程序求出升学班学生得分的最低分。

输入格式

输入按以下格式给出。

$N$
$A_1\ \ A_2\ \ \dots\ \ A_N$

输出格式

输出一行：升学班学生得分的最低分。

3
1000 500 800

1000

6
100 75 41 75 13 89

89

6
20 25 12 7 13 16

16

8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534

364353982

提示

样例解释

样例 $1$ 解释

例如，令 $x = 900$，则学生 $1$ 被分到升学班，学生 $2, 3$ 被分到普通班。

另一种可能的分班方式是，将学生 $1, 3$ 分到升学班，将学生 $2$ 分到普通班。比如令 $x = 800$ 就可以实现这一点。

这两种分法中，升学班人数与普通班人数之差都为 $1$。因此，会选择升学班人数最少的前一种分法。此时，升学班学生得分的最低分是 $1\,000$ 分。

该输入样例满足所有子任务的约束。

样例 2 解释

令 $x = 89$，则学生 $1, 6$ 被分到升学班，学生 $2, 3, 4, 5$ 被分到普通班。此时升学班学生得分的最低分为 $89$ 分。

该输入样例满足子任务 4 的约束。

样例 $3$ 解释

该输入样例满足子任务 3, 4 的约束。

样例 $4$ 解释

该输入样例满足子任务 4 的约束。

约束

• $2 \le N \le 500\,000$。
• $1 \le A_i \le 10^9$（$1 \le i \le N$）。
• 存在 $i, j$（$1 \le i < j \le N$）使得 $A_i \ne A_j$。
• 输入的值均为整数。

子任务

• $\text{(20 pts)}$：$N = 3$。
• $\text{(20 pts)}$：$A_i$ 为 $500, 800, 1\,000$ 之一（$1 \le i \le N$）。
• $\text{(20 pts)}$：$A_i \ne A_j$（$1 \le i < j \le N$）。
• $\text{(40 pts)}$：无额外约束。