题目描述

白糖糕是一种流行于南昌民间的传统糕类小吃，起源于明清时期，被誉为“江西五大传统名点”。其特点香糯、柔软、洁白，造型上与一般白糖糕比独具一格，风味独特，深受大家喜爱。Orange_lce作为南昌人，从小就很喜欢吃白糖糕。这道菜也是亲朋好友聚会时，饭桌上必不可少的一道甜品。

在 Orange_Ice 的印象中，白糖糕外观是雪白的。然而每次和奶奶提起白糖糕时，作为老南昌人的她总会感慨：“现在的白糖糕都是雪白雪白的，我们那时候吃的白糖糕都是带一些淡黄色的，那个才正宗！” 这一说法激起了 Orange_ice 的兴致，他决定前往南昌老城区--万寿宫、大士院一带，寻找老一辈人吃的正宗白糖糕。

在老城区，Orange_Ice发现了$n$家售卖白糖糕的店铺。由于每家店的工艺略有不同，糕点的颜色是深浅不一的，而他无法确定奶奶所说的“淡黄色”究竟长什么样子。为了尽可能找到最正宗的白糖糕，他将第$i$家白糖糕所带黄色的程度用一个非负整数$a_i$表示，称为“色泽”，其中$a_i\in [0,k]$,数值越小表示糕点越白，数值越大则表示越黄。

由于预算有限，他最多只能购买$m$家店铺的白糖糕。为了保证无论奶奶心中的那个“标准色”是多少，他都能拿出一块色泽最接近$x$的糕点，他决定这样规划:他要挑选不超过$m$家店铺购买，使得最坏情况下（即对于所有可能的$x$)，手中的糕点色泽最接近于$x$的值，与$x$的差距尽可能小。注意：$x \in [0,k]$，且为整数。

形式化地说，设选定的店铺集合为$S$，定义对于任意目标色泽$x$的偏差为$f(x,S)=min|x-s|$。目标是 求出最小的最坏偏差 ans:

$$\text { ans }=\min _{\substack{S \subseteq\left\{a_{1} \ldots, a_{n}\right\} \\|S| \leq m}}\left(\max _{x \in[0, k]} f(x, S)\right)=\min _{\substack{S \subseteq\left\{a_{1}, \ldots, a_{n}\right\} \\|S| \leq m}}\left(\max _{x \in[0, k]} \min _{s \in S}|x-s|\right)$$

请你帮 Orange_Ice 计算，这个"最坏情况下的最小偏差”是多少？

输入格式

第一行包含三个整数$n,m,k$，分别代表店铺数量、最多能购买的店铺数量和“色泽”的上限值。 第二行包含$n$个整数，表示第$i$家店铺的白糖糕的色泽值为$a_i$。 对于全部数据，满足$1 \le m \le n \le 5 \times 10^5，0 \le a_i \le k \le 10^{12}$ 来自Orange_Ice 的提示：本题读入量较大，建议选用较快的读入方式，尤其是非C/C++语言。

输出格式

仅一行一个整数，表示最坏情况下的最小偏差，具体含义见题面描述。

5 3 20
18 2 8 3 15

5

5 2 20
2 2 11 5 9

9

解释 #1

数据范围

额外挑战