配点 : $300$ 点

問題文

高橋君は、 $N$ 個の競技プログラミング用の問題をつくりました。 それぞれの問題には $1$ から $N$ の番号がついており、問題 $i$ の難易度は整数 $d_i$ で表されます(大きいほど難しいです)。

高橋君はある整数 $K$ を決めることで、

• 難易度が $K$ 以上ならば「 $ARC$ 用の問題」
• 難易度が $K$ 未満ならば「 $ABC$ 用の問題」

という風に、これらの問題を二種類に分類しようとしています。

「$ARC$ 用の問題」と「$ABC$ 用の問題」が同じ数になるような整数 $K$ の選び方は何通りあるでしょうか。

制約

• $2 \leqq N \leqq 10^5$
• $N$ は偶数である。
• $1 \leqq d_i \leqq 10^5$
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられます。

$N$

$d_1$ $d_2$ $...$ $d_N$

出力

「$ARC$ 用の問題」と「$ABC$ 用の問題」が同じ数になるような整数 $K$ の選び方の数を出力してください。

6
9 1 4 4 6 7

2

$K=5,6$ としたとき、問題 $1,5,6$ が「$ARC$ 用の問題」、問題 $2,3,4$ が「$ABC$ 用の問題」となり、条件を満たします。 よって、答えは $2$ 通りです。

8
9 1 14 5 5 4 4 14

0

「$ARC$ 用の問題」と「$ABC$ 用の問題」が同じ数になるような整数 $K$ の選び方が存在しない場合もあります。

14
99592 10342 29105 78532 83018 11639 92015 77204 30914 21912 34519 80835 100000 1

42685