AT_joi2026_yo2_a クラス分け (Class Division)

JOI 高校の 1 年生は全部で $ N $ 人であり， $ 1 $ から $ N $ までの番号が付けられている． ある日，1 年生 $ N $ 人は試験を受験した．生徒 $ i $ ( $ 1 \leqq i \leqq N $ ) の得点は $ A_i $ 点であった．ここで， $ N $ 人全員が同じ得点を取ったわけではなかった． この試験の成績によって来年度のクラス分けが決定される．具体的には，ある整数 $ x $ が選ばれて，得点が $ x $ 点以上の生徒は**進学クラス**，得点が $ x $ 点未満の生徒は**普通クラス**となるように $ N $ 人の生徒が $ 2 $ クラスに分けられる． ここで，それぞれのクラスには $ 1 $ 人以上の生徒が属するようにし，また進学クラスの生徒の数と普通クラスの生徒の数の差が最小となるような分け方が選ばれる．更に，そのような分け方が複数考えられる場合は，その中で進学クラスの人数が最小となるような分け方が選ばれる． 生徒の数とそれぞれの生徒の得点が与えられたとき，進学クラスの生徒の得点の最低点を求めるプログラムを作成せよ．

入力は以下の形式で与えられる． > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

進学クラスの生徒の得点の最低点を $ 1 $ 行で出力せよ．

### 小課題 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 $ 点) 追加の制約はない． ### Sample Explanation 1 例えば， $ x = 900 $ とすると，生徒 $ 1 $ は進学クラスに，生徒 $ 2, 3 $ は普通クラスに振り分けられる． 考えられるもう一つの生徒の分け方は，生徒 $ 1, 3 $ を進学クラスに，生徒 $ 2 $ を普通クラスに振り分けるものである．これは例えば $ x = 800 $ とすれば実現できる． この $ 2 $ つの分け方は，どちらも進学クラスの生徒の数と普通クラスの生徒の数の差は $ 1 $ となる．よって，進学クラスの生徒の数が最小となる分け方である前者が選ばれる．このとき，進学クラスの生徒の得点の最低点は $ 1\,000 $ 点である． この入力例はすべての小課題の制約を満たす． ### Sample Explanation 2 $ x = 89 $ とすると，生徒 $ 1, 6 $ が進学クラスに振り分けられ，生徒 $ 2, 3, 4, 5 $ が普通クラスに振り分けられる．このとき進学クラスの生徒の得点の最低点は $ 89 $ 点である． この入力例は小課題 $ 4 $ の制約を満たす． ### Sample Explanation 3 この入力例は小課題 $ 3, 4 $ の制約を満たす． ### Sample Explanation 4 この入力例は小課題 $ 4 $ の制約を満たす． ### Constraints - $ 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 $ ． - 入力される値はすべて整数である．