P14795 [JOI 2026 二次预选] 分班 / Class Division

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$

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

### 样例解释 #### 样例 $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)}$：无额外约束。