3975. 图书馆

【题目背景】

为了满足市民的阅读需求，C市准备建立一个人性化的图书馆。

【题目描述】

图书馆的书架高度对于读者来说非常重要，每个人都有自己舒适的阅读高度，图书馆希望尽量为读者提供舒适的阅读环境，因此他们计划安装多个不同高度的书架，以满足大多数读者的高度需求。

但图书馆当前面临一个挑战：他们既想满足超过一半的读者的高度需求，又想让书架的高度变化范围尽可能小（最大高度与最小高度的差值尽可能的小），以保持图书馆环境的统一性和协调性。

为了解决这个问题，图书馆决定先收集 $N$ 个读者的阅读高度偏好，并将高度按照从小到大的顺序进行排列完毕。现在，请你帮助图书馆计算满足条件的最小书架高度差是多少。

【输入格式】

第 $1$ 行 :  一个整数 $N$ ，代表读者的个数。

第 $2 \sim N+1$ 行 :  一个整数 $a_i$，表示第 $i$ 个读者舒适的阅读高度。

【输出格式】

一行，最高的书架和最低的书架之间的高度差。

【样例1输入】

3
2
3
18

【样例1输出】

1

【样例2输入】

5
8
9
10
10
10

【样例2输出】

0

【样例说明】

对于样例 $1$：需要满足至少 $2$ 个读者的阅读高度，考虑书架的高度为：$2、3$，高度差为 $1$ 。

对于样例 $2$：需要满足至少 $3$ 个读者的阅读高度，考虑书架的高度为：$10$，高度差为 $0$ 。

【数据规模与约定】

对于 $100\%$ 的测试数据，$3 \leq N \leq 100000$ , $1 \leq a_i \leq 10^7$。

【来源】

2024年校际联合邀请赛 语法组-第2场 Task4