問題文

JOI 高校の 1 年生は全部で N 人であり，1 から N までの番号が付けられている．

ある日，1 年生 N 人は試験を受験した．生徒 i (1 \leqq i \leqq N) の得点は A_i 点であった．ここで，N 人全員が同じ得点を取ったわけではなかった．

この試験の成績によって来年度のクラス分けが決定される．具体的には，ある整数 x が選ばれて，得点が x 点以上の生徒は進学クラス，得点が x 点未満の生徒は普通クラスとなるように N 人の生徒が 2 クラスに分けられる．

ここで，それぞれのクラスには 1 人以上の生徒が属するようにし，また進学クラスの生徒の数と普通クラスの生徒の数の差が最小となるような分け方が選ばれる．更に，そのような分け方が複数考えられる場合は，その中で進学クラスの人数が最小となるような分け方が選ばれる．

生徒の数とそれぞれの生徒の得点が与えられたとき，進学クラスの生徒の得点の最低点を求めるプログラムを作成せよ．

制約

• 2 \leqq N \leqq 500\,000．
• 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)．
• ある i, j (1 \leqq i < j \leqq N) が存在して A_i \neq A_j．
• 入力される値はすべて整数である．

小課題

1. (20 点) N = 3．
2. (20 点) A_i は 500, 800, 1\,000 のいずれかである (1 \leqq i \leqq N)．
3. (20 点) A_i \neq A_j (1 \leqq i < j \leqq N)．
4. (40 点) 追加の制約はない．

入力例 1

3
1000 500 800

出力例 1

1000

例えば，x = 900 とすると，生徒 1 は進学クラスに，生徒 2, 3 は普通クラスに振り分けられる．

考えられるもう一つの生徒の分け方は，生徒 1, 3 を進学クラスに，生徒 2 を普通クラスに振り分けるものである．これは例えば x = 800 とすれば実現できる．

この 2 つの分け方は，どちらも進学クラスの生徒の数と普通クラスの生徒の数の差は 1 となる．よって，進学クラスの生徒の数が最小となる分け方である前者が選ばれる．このとき，進学クラスの生徒の得点の最低点は 1\,000 点である．

この入力例はすべての小課題の制約を満たす．

入力例 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 の制約を満たす．