分数: 300 点
问题陈述
高桥制作 N 竞争性编程问题。 问题已数出 1 to N,以及问题的难度 i 表示为整数 d_i (越高,越难)。
他通过选择一个整数将问题分为两类 K,如下:
- 一个有难度的问题 K 或更高版本将 用于 ARC.
- 一道难度低于 K 将是 对于 ABC.
整数有多少种选择 K 使 ARC 的问题数量和 ABC 的问题数量相同吗?
问题陈述
- 2 \leq N \leq 10^5
- N 是偶数。
- 1 \leq d_i \leq 10^5
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N d_1 d_2 ... d_N
输出
打印整数的选择个数 K 使得 ARC 的问题数量和 ABC 的问题数量相同。
示例输入 1
6 9 1 4 4 6 7
示例输出 1
2
如果我们选择 K=5 or 6,问题 1, 5,和 6 将用于 ARC,问题 2, 3,和 4 将用于ABC,目标已达到。 因此,答案是 2.
示例输入 2
8 9 1 14 5 5 4 4 14
示例输出 2
0
可能无法选择整数 K 使得 ARC 的问题数量和 ABC 的问题数量相同。
示例输入 3
14 99592 10342 29105 78532 83018 11639 92015 77204 30914 21912 34519 80835 100000 1
示例输出 3
42685