레이팅 미적용JOI 高校の 1 年生は全部で N 人であり, 1 から N までの番号が付けられている.
ある日,1 年生 N 人は試験を受験した.生徒 i ( \(1 \le i \le N\) ) の得点は A i 点であった.ここで, N 人全員が同じ得点を取ったわけではなかった.
この試験の成績によって来年度のクラス分けが決定される.具体的には,ある整数 x が選ばれて,得点が x 点以上の生徒は 進学クラス ,得点が x 点未満の生徒は 普通クラス となるように N 人の生徒が 2 クラスに分けられる.
ここで,それぞれのクラスには 1 人以上の生徒が属するようにし,また進学クラスの生徒の数と普通クラスの生徒の数の差が最小となるような分け方が選ばれる.更に,そのような分け方が複数考えられる場合は,その中で進学クラスの人数が最小となるような分け方が選ばれる.
生徒の数とそれぞれの生徒の得点が与えられたとき,進学クラスの生徒の得点の最低点を求めるプログラムを作成せよ.
2 ≦ N ≦ 500 000 .
1 ≦ A i ≦ 10 9 ( \(1 \le i \le N\) ).
ある i, j ( \(1 \le i < j \le N\) ) が存在して A i ≠ A j .
入力される値はすべて整数である.
( 20 点) N = 3 .
( 20 点) A i は 500 , 800 , 1 000 のいずれかである ( \(1 \le i \le N\) ).
( 20 点) A i ≠ A j ( \(1 \le i < j \le N\) ).
( 40 点) 追加の制約はない.
入力は以下の形式で与えられる.
N
A 1 A 2 ... A N
進学クラスの生徒の得点の最低点を 1 行で出力せよ.
3
1000 500 800
1000
6
100 75 41 75 13 89
89
6
20 25 12 7 13 16
16
8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534
364353982