Problem Statement

There are a total of $N$ $1$-st year students at JOI High School, numbered from $1$ to $N$.

One day, the $N$ $1$-st year students took an exam. The score of student $i$ ($1 \le i \le N$) was $A_i$ points. Here, not all $N$ students got the same score.

Based on the results of this exam, the class division for the next school year is determined. Specifically, an integer $x$ is chosen, and the $N$ students are divided into $2$ classes such that students with a score of $x$ points or more are placed in the Advanced Class, and students with a score of less than $x$ points are placed in the Regular Class.

Here, a division is chosen such that at least $1$ student belongs to each class, and the difference between the number of students in the Advanced Class and the number of students in the Regular Class is minimized. Furthermore, if there are multiple such divisions, the one among them that minimizes the number of students in the Advanced Class is chosen.

Given the number of students and the score of each student, write a program to find the minimum score among the students in the Advanced Class.

Constraints

• $2 \le N \le 500000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• There exist $i, j$ ($1 \le i < j \le N$) such that $A_i \ne A_j$.
• All input values are integers.

Subtasks

1. ($20$ points) $N = 3$.
2. ($20$ points) $A_i$ is one of $500, 800, 1000$ ($1 \le i \le N$).
3. ($20$ points) $A_i \ne A_j$ ($1 \le i < j \le N$).
4. ($40$ points) There are no additional constraints.

Input

The input is given in the following format:

N
A_1 A_2 ... A_N

Output

Output the minimum score among the students in the Advanced Class in $1$ line.

Sample Input and Output

Sample Input $1$

3
1000 500 800

Sample Output $1$

1000

For example, if $x = 900$, student $1$ is assigned to the Advanced Class, and students $2, 3$ are assigned to the Regular Class.

Another possible way to divide the students is to assign students $1, 3$ to the Advanced Class and student $2$ to the Regular Class. This can be achieved, for example, by setting $x = 800$.

In both of these $2$ ways of dividing, the difference between the number of students in the Advanced Class and the number of students in the Regular Class is $1$. Therefore, the former division, which minimizes the number of students in the Advanced Class, is chosen. At this time, the minimum score among the students in the Advanced Class is $1000$ points.

This sample input satisfies the constraints of all subtasks.

Sample Input $2$

6
100 75 41 75 13 89

Sample Output $2$

89

If $x = 89$, students $1, 6$ are assigned to the Advanced Class, and students $2, 3, 4, 5$ are assigned to the Regular Class. At this time, the minimum score among the students in the Advanced Class is $89$ points.

This sample input satisfies the constraints of Subtask $4$.

Sample Input $3$

6
20 25 12 7 13 16

Sample Output $3$

16

This sample input satisfies the constraints of Subtasks $3, 4$.

Sample Input $4$

8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534

Sample Output $4$

364353982

This sample input satisfies the constraints of Subtask $4$.