C - Divide the Problems Editorial /

Time Limit: 2 sec / Memory Limit: 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