配点: 100 点
問題文
JOI高中所有一年级学生 N 是一个人, 它们的编号最大为1 从 N 。
有一天,一年级学生 N 此人参加了考试。学生 i (1 \leqq i \leqq N) 的分数是 A_i 点。在这里,N 并非每个人都得到相同的分数。
明年的班级安排将根据本次考试的结果确定。具体来说,一些整数 选择 x ,得分为 x 积分或以上的学生预备班,得分为 x 学生少于普通班以便 N 学生 2 它分为类。
这里,每个班级都有 1 选择划分方法,使一个以上的学生属于一个班级,并将高级班的学生人数与普通班的学生人数之间的差异最小化。此外,如果可以有多个这样的班级,则选择使预科班学生人数最少的一个。
给定学生人数和每个学生的分数,编写一个程序找出预科班学生的最低分数。
制約
- 2 \leqq N \leqq 500\,000.
- 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
- 是 i, j (1 \leqq i < j \leqq N) 存在 是 A_i \neq A_j.
- 所有输入值都是整数。
小課題
- (20 点) N = 3.
- (20 点) A_i 表示 500, 800, 1\,000 (1 \leqq i \leqq N).
- (20 点) A_i \neq A_j (1 \leqq i < j \leqq N).
- (40 点)没有额外的限制。
入力
输入按以下格式给出。
N A_1 A_2 \cdots A_N
出力
预科班学生成绩最低 1 行。
入力例 1
3 1000 500 800
出力例 1
1000
例如,x = 900 然后学生 1 是预科班的学生。 2, 3 被分配到普通班级。
划分学生的另一种可能方法是 1, 3 致预科班同学们 2 分为普通班。这是例如 这可以通过 x = 800 来实现。
这个 2 两种情况下,预科班学生人数与普通班学生人数之差为 1 变为。因此,选择前一种方式,因为这样可以最大限度地减少预科班的学生人数。此时,预科班学生的最低成绩是 1\,000 点。
此输入示例满足所有子任务约束。
入力例 2
6 100 75 41 75 13 89
出力例 2
89
x = 89 然后学生 1, 6 被分配到预科班,学生 2, 3, 4, 5 被分配到普通班级。此时,预科班学生的最低成绩是 89 点。
此输入示例是一个小作业。 4 满足约束。
入力例 3
6 20 25 12 7 13 16
出力例 3
16
此输入示例是一个小作业。 3, 4 满足约束。
入力例 4
8 364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534
出力例 4
364353982
此输入示例是一个小作业。 4 满足约束。