← 返回题目列表

AtCoder · abc132_c

C. 划分问题

中文机器翻译题面 查看原题

分数: 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