題目描述

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$ 嘅限制。