JOI 고등학교 1학년은 모두 \(N\)명이며, 1부터 \(N\)까지 번호가 붙어 있다. 어느 날, 1학년 \(N\)명이 시험을 치렀다. 학생 \(i\) (\(1 \le i \le N\))의 득점은 \(A_i\)점이었다. \(N\)명 전원이 같은 득점을 받은 것은 아니다. 이 시험 성적에 따라 내년도 클래스 분배가 정해진다. 구체적으로, 어떤 정수 \(x\)가 정해져, 득점이 \(x\)점 이상인 학생은 진학 클래스, 득점이 \(x\)점 미만인 학생은 보통 클래스가 되도록 \(N\)명의 학생이 2개 클래스로 나뉜다. 각 클래스에는 1명 이상의 학생이 속하도록 하며, 진학 클래스 학생 수와 보통 클래스 학생 수의 차가 최소가 되는 분배가 선택된다. 더욱이, 그러한 분배가 여러 가지 가능하면, 그중 진학 클래스 인원이 최소가 되는 분배가 선택된다. 학생 수와 각 학생의 득점이 주어졌을 때, 진학 클래스 학생 득점의 최솟값을 구하는 프로그램을 작성하라. |
입력은 다음 형식으로 주어진다.
\(N\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
제약 조건
- \(2 \le N \le 500{,}000\)
- \(1 \le A_i \le 10^9\) (\(1 \le i \le N\))
- \(1 \le i < j \le N\)을 만족하는 \(i, j\)가 존재하여 \(A_i \ne A_j\)이다.
- 입력되는 값은 모두 정수이다.
부분문제
- (20점) \(N = 3\)
- (20점) \(A_i\)는 500, 800, 1,000 중 하나이다 (\(1 \le i \le N\)).
- (20점) \(A_i \ne A_j\) (\(1 \le i < j \le N\)).
- (40점) 추가 제약 조건 없음.
다음 형식으로 출력한다.
진학 클래스 학생 득점의 최솟값을 1줄에 출력한다.
예를 들어 \(x = 900\)으로 하면, 학생 1은 진학 클래스, 학생 2, 3은 보통 클래스로 배정된다.
가능한 다른 분배는 학생 1, 3을 진학 클래스에, 학생 2를 보통 클래스에 배정하는 것이다. 이는 예를 들어 \(x = 800\)으로 실현할 수 있다.
이 두 분배는 모두 진학 클래스와 보통 클래스 학생 수의 차가 1이다. 따라서 진학 클래스 인원이 최소인 전자가 선택된다. 이때 진학 클래스 학생 득점의 최솟값은 1,000점이다.
\(x = 89\)로 하면, 학생 1, 6이 진학 클래스에 배정되고, 학생 2, 3, 4, 5가 보통 클래스에 배정된다. 이때 진학 클래스 학생 득점의 최솟값은 89점이다.