Divide the Problems

题目描述

Takahashi 制作了 $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$

输出格式

打印使得用于 ARCs 的题目数量与用于 ABCs 的题目数量相同的整数 $K$ 的选择个数。

6
9 1 4 4 6 7

2

8
9 1 14 5 5 4 4 14

0

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

42685

提示

如果我们选择 $K=5$ 或 $6$，第 $1$、$5$、$6$ 题将用于 ARCs，第 $2$、$3$、$4$ 题将用于 ABCs，目标得以实现。 因此，答案是 $2$.
也可能不存在任何使得用于 ARCs 的题目数量与用于 ABCs 的题目数量相同的整数 $K$。

标签: AtCoder|abc132C

来源

AtCoder|abc132C