AT_joi2026_yo2_a クラス分け (Class Division)

JOI 高校的一年级学生共有 $N$ 人，编号从 $1$ 到 $N$。 某天，这 $N$ 名一年级学生参加了一场考试。第 $i$ 位学生的分数为 $A_i$。这里，所有 $N$ 名学生的分数不全相同。 根据本次考试的成绩，将决定下一学年的班级分组。具体来说，会选择一个整数 $x$，分数不低于 $x$ 的学生被分入“进学班”，分数低于 $x$ 的学生被分入“普通班”，将 $N$ 名学生分为两个班级。 分班时，需要满足以下条件：每个班级至少有 $1$ 名学生；同时，应选择使进学班人数和普通班人数的差的绝对值最小的分法。同时，如果存在多种符合上述要求的分法，则选择其中进学班人数最少的那一种。 现给定学生人数及各自的分数，编写程序求出进学班学生的分数最低线。

输入格式如下： > $N$ $A_1$ $A_2$ $\cdots$ $A_N$

请在一行输出进学班中学生的分数最低线。

## 子任务 1. ($20$ 分) $N = 3$。 2. ($20$ 分) 所有 $A_i$ 均为 $500, 800, 1\,000$ 中的某个数（$1 \leq i \leq N$）。 3. ($20$ 分) $A_i \neq A_j$（$1 \leq i < j \leq N$）。 4. ($40$ 分) 无额外限制。 ## 样例解释 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 \leq N \leq 500\,000$。 - $1 \leq A_i \leq 10^9$（$1 \leq i \leq N$）。 - 存在某 $i, j$（$1 \leq i < j \leq N$），使得 $A_i \neq A_j$。 - 输入均为整数。 由 ChatGPT 5 翻译