划分题目

题目描述

高桥君制作了 $N$ 道编程竞赛题。每道题都标有编号 $1$ 到 $N$,题目 $i$ 的难度用整数 $d_i$ 表示(数值越大越难)。

高桥君通过确定某个整数 $K$,把这些问题分成两类:

• 难度大于等于 $K$ 的为「用于 ARC 的题目」

• 难度小于 $K$ 的为「用于 ABC 的题目」

有多少种整数 $K$ 的选法,能使「用于 ARC 的题目」和「用于 ABC 的题目」数量相同?

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出能使「用于 ARC 的题目」和「用于 ABC 的题目」数量相同的整数 $K$ 的选法数量。

样例

6
9 1 4 4 6 7

2

取 $K=5,6$ 时,题目 $1,5,6$ 成为「用于 ARC 的题目」,题目 $2,3,4$ 成为「用于 ABC 的题目」,满足条件。

因此答案是 2 种。

8
9 1 14 5 5 4 4 14

0

也可能不存在能使「用于 ARC 的题目」和「用于 ABC 的题目」数量相同的整数 $K$。

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

42685

数据范围

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