AT_abc132_c [ABC132C] Divide the Problems

题目描述

高桥君制作了 $N$ 个用于竞赛编程的问题。每个问题都编号为 $1$ 到 $N$，问题 $i$ 的难度用整数 $d_i$ 表示（数值越大表示越难）。

高桥君想通过选择一个整数 $K$，将这些问题分为两类：

• 难度大于等于 $K$ 的问题为“ARC 用的问题”；
• 难度小于 $K$ 的问题为“ABC 用的问题”。

请问，有多少种选择整数 $K$ 的方法，可以使“ARC 用的问题”和“ABC 用的问题”的数量相同？

输入格式

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

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

输出格式

输出可以使“ARC 用的问题”和“ABC 用的问题”数量相同的整数 $K$ 的选择方法数。

样例 1

输入

6
9 1 4 4 6 7

输出

2

样例 2

输入

8
9 1 14 5 5 4 4 14

输出

0

样例 3

输入

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

输出

42685

说明/提示

限制条件

• $2 \leq N \leq 10^5$
• $N$ 是偶数。
• $1 \leq d_i \leq 10^5$
• 输入均为整数。

样例解释 1

当 $K=5,6$ 时，问题 $1,5,6$ 被分为“ARC 用的问题”，问题 $2,3,4$ 被分为“ABC 用的问题”，满足条件。因此，答案为 $2$ 种。

样例解释 2

也有可能不存在可以使“ARC 用的问题”和“ABC 用的问题”数量相同的整数 $K$ 的选择方法。

由 ChatGPT 4.1 翻译