題目描述

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