You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

光头强是一家大型图书馆的管理员。最近，图书馆收到了一批新书，共计 ( $N$ ) 本。每本书都有一个独特的编号（从 $1$ 到 ( $N$ )），并且每本书的阅读难度用一个整数 ( $d_i$ ) 表示（数值越大，书越难读）。

为了帮助读者更好地选择书籍，光头强决定将这些书划分为两类：

• 高级书籍（Advanced Books）：阅读难度大于或等于某个阈值 ( $K$ ) 的书籍。
• 初级书籍（Basic Books）：阅读难度小于 ( $K$ ) 的书籍。

光头强希望找到一种划分方式，使得 高级书籍 和 初级书籍 的数量 完全相同。由于图书馆的书籍数量 ( $N$ ) 是偶数，因此这种划分是可能的。

你的任务是帮助光头强计算，有多少种选择阈值 ( $K$ ) 的方式，可以满足上述条件。

题目描述

给定 ( $N$ ) 本书的阅读难度 ( $d_1, d_2, \dots, d_N$ )，你需要找到一个整数 ( $K$ )，使得：

• 阅读难度 大于或等于 ( $K$ ) 的书籍数量等于阅读难度 小于 ( $K$ ) 的书籍数量。

输出满足条件的 ( $K$ ) 的选择方式的数量。

输入

• 第一行包含一个整数 ( $N$ )，表示书籍的数量。
• 第二行包含 ( $N$ ) 个整数 ( $d_1, d_2, \dots, d_N$ )，表示每本书的阅读难度。

输出

输出一个整数，表示满足条件的 ( $K$ ) 的选择方式的数量。

6
9 1 4 4 6 7

2

样例解释

如果选择 $K= 5$或$6$，问题1、5和6将被划为"高级书籍”，问题2、3和4将被划为“低级书籍”，目标就能够实现。 因此，答案是2

8
9 1 14 5 5 4 4 14

0

样例解释

可能没有选择整数$K$的方式能够使得“高级书籍”的问题数量和“低级书籍”的问题数量相同。

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

42685

提示

$2 \leq N \leq 10^5$

$1 \leq d_i \leq 10^5$

$N$ 一定是偶数