문제 설명

JOI 고등학교의 $1$ 학년 학생은 총 $N$ 명이며, $1$ 부터 $N$ 까지의 번호가 붙어 있다.

어느 날, $1$ 학년 학생 $N$ 명은 시험을 치렀다. 학생 $i$ ($1 \le i \le N$) 의 점수는 $A_i$ 점이었다. 여기서 $N$ 명 전원이 같은 점수를 받은 것은 아니었다.

이 시험 성적에 따라 내년도 반 배정이 결정된다. 구체적으로는 어떤 정수 $x$ 가 선택되어, 점수가 $x$ 점 이상인 학생은 진학반, 점수가 $x$ 점 미만인 학생은 보통반이 되도록 $N$ 명의 학생이 $2$ 개의 반으로 나뉜다.

여기서 각 반에는 $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$ 의 제약 조건을 만족한다.