10206: ABC132 - C - Divide the Problems
[Creator : ]
Description
### 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?
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?
Input
Input is given from Standard Input in the following format:
```
$N$
$d_1$ $d_2$ $...$ $d_N$
```
```
$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.
Constraints
- $2 \leq N \leq 10^5$
- $N$ is an even number.
- $1 \leq d_i \leq 10^5$
- All values in input are integers.
- $N$ is an even number.
- $1 \leq d_i \leq 10^5$
- All values in input are integers.
Sample 1 Input
6
9 1 4 4 6 7
Sample 1 Output
2
If we choose K=5 or 66, 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 2 Input
8
9 1 14 5 5 4 4 14
Sample 2 Output
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 3 Input
14
99592 10342 29105 78532 83018 11639 92015 77204 30914 21912 34519 80835 100000 1
Sample 3 Output
42685