実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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 の選び方の数を出力してください。
入力例 1
6 9 1 4 4 6 7
出力例 1
2
K=5,6 としたとき、問題 1,5,6 が「ARC 用の問題」、問題 2,3,4 が「ABC 用の問題」となり、条件を満たします。 よって、答えは 2 通りです。
入力例 2
8 9 1 14 5 5 4 4 14
出力例 2
0
「ARC 用の問題」と「ABC 用の問題」が同じ数になるような整数 K の選び方が存在しない場合もあります。
入力例 3
14 99592 10342 29105 78532 83018 11639 92015 77204 30914 21912 34519 80835 100000 1
出力例 3
42685
Score : 300 points
Problem Statement
Takahashi made N problems for competitive programming. The problems are numbered 1 to N, and the difficulty of Problem i is represented as an integer d_i (the higher, the harder).
He is dividing the problems into two categories by choosing an integer K, as follows:
- A problem with difficulty K or higher will be for ARCs.
- A problem with difficulty lower than K will be for ABCs.
How many choices of the integer K make the number of problems for ARCs and the number of problems for ABCs the same?
Problem Statement
- 2 \leq N \leq 10^5
- N is an even number.
- 1 \leq d_i \leq 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N d_1 d_2 ... d_N
Output
Print the number of choices of the integer K that make the number of problems for ARCs and the number of problems for ABCs the same.
Sample Input 1
6 9 1 4 4 6 7
Sample Output 1
2
If we choose K=5 or 6, Problem 1, 5, and 6 will be for ARCs, Problem 2, 3, and 4 will be for ABCs, and the objective is achieved. Thus, the answer is 2.
Sample Input 2
8 9 1 14 5 5 4 4 14
Sample Output 2
0
There may be no choice of the integer K that make the number of problems for ARCs and the number of problems for ABCs the same.
Sample Input 3
14 99592 10342 29105 78532 83018 11639 92015 77204 30914 21912 34519 80835 100000 1
Sample Output 3
42685