题目描述

JOI 高中的 $1$ 年级学生共有 $N$ 人，编号为 $1$ 到 $N$。

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

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

这里，要求每个班至少有 $1$ 名学生，并且选择使升学班学生人数与普通班学生人数之差最小的分法。此外，如果有多种这样的分法，则选择其中升学班人数最小的分法。

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

数据范围

• $2 \le N \le 500000$。
• $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$。
• 输入的所有值均为整数。

子任务

1. （$20$ 分）$N = 3$。
2. （$20$ 分）$A_i$ 为 $500, 800, 1000$ 之一（$1 \le i \le N$）。
3. （$20$ 分）$A_i \ne A_j$（$1 \le i < j \le N$）。
4. （$40$ 分）无附加限制。

输入格式

输入按以下格式给出：

N
A_1 A_2 ... A_N

输出格式

输出 $1$ 行，表示升学班学生得分的最低分。

样例输入与输出

样例输入 $1$

3
1000 500 800

样例输出 $1$

1000

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

另一种可行的分法是将学生 $1, 3$ 分入升学班，将学生 $2$ 分入普通班。这可以通过例如取 $x = 800$ 来实现。

在这 $2$ 种分法中，升学班学生人数与普通班学生人数之差均为 $1$。因此，选择升学班学生人数最小的前一种分法。此时，升学班学生得分的最低分为 $1000$ 分。

该样例输入满足所有子任务的限制。

样例输入 $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$ 的限制。