C - 划分问题

得分：300分

问题描述

高桥为竞技编程设计了$N$个问题。 问题的编号为$1$至$N$，问题$i$的难度用整数$d_i$表示（数值越大，问题越难）。

他通过选择一个整数$K$将问题划分为两个类别，规则如下：

• 难度大于等于$K$的问题将被划为“ARCs”。
• 难度小于$K$的问题将被划为“ABCs”。

有多少种选择整数$K$的方式可以使得“ARCs”的问题数量和“ABCs”的问题数量相同？

问题描述

• $2 \leq N \leq 10^5$
• $N$为偶数。
• $1 \leq d_i \leq 10^5$
• 输入中所有的值都是整数。

输入

输入以以下格式从标准输入中给出：

$N$

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

输出

输出选择整数$K$的方式的数量，使得“ARCs”的问题数量和“ABCs”的问题数量相同。

6
9 1 4 4 6 7

2

如果选择$K=5$或$6$，问题$1$、$5$和$6$将被划为“ARCs”，问题$2$、$3$和$4$将被划为“ABCs”，目标就能够实现。 因此，答案是$2$。

8
9 1 14 5 5 4 4 14

0

可能没有选择整数$K$的方式能够使得“ARCs”的问题数量和“ABCs”的问题数量相同。

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

42685