配点 : 300 点
問題文
长度 小于或等于 N 的非负整数序列 A=(A_1,A_2,\dots,A_N) 和一个正整数 对 M,K 。 这里,一个整数 按值升序对 x ,f(x) 如下。
- 长度 小于或等于 N 的非负整数序列 B 该值应乘以 B_i=|A_i-x| 中定义。B 进行排序时, 您最多可以选择 B_M 的值为 f(x) 。
现在你 A 的元素 我试图通过重写最多 0 個以上 K 并将其更改为任何其他非负整数。这时, 找到 f(x) 的最小可能整数。
制約
- 1 \leq N \leq 5 \times 10^5
- 1\leq M \leq N
- 0\leq K \leq N
- 0\leq A_i \leq 10^9
- 所有输入均为整数。
入力
输入是按以下格式从标准输入给出的。
N M K A_1 A_2 \dots A_N
出力
将答案输出在一行。
入力例 1
5 3 1 1 4 2 8 5
出力例 1
1
入力例 2
6 3 1 30 50 80 85 95 120
出力例 2
3