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 翻译