题目描述

長さ $N$ の数列 $A$ と整数 $K$ が与えられます。 この配列に、以下の操作を $Q$ 回行います。

• 長さ $K$ の連続する部分列を $1$ つ選ぶ。 そして、選んだ部分列に含まれる $K$ 個の要素のうち最小のもの（複数ある場合はその中で好きなものを $1$ 個）を取り除く。

$Q$ 回の操作で取り除いた要素の最大値、最小値をそれぞれ $X$, $Y$ としたときに、$X-Y$ をできるだけ小さくしたいです。 $Q$ 回の操作を適切に行ったときの $X-Y$ の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $Q$ $A_1$ $A_2$ $...$ $A_N$

输出格式

$X-Y$ の最小値を出力せよ。

题目大意

题目描述

你有一个长度为 $n$ 的整数序列 $A$，以及一个整数 $K$。你会进行 $Q$ 次操作，一次操作如下：

• 选择序列中一个长度为 $K$ 的区间，并且删除区间中的最小元素。如果有多个，你可以选择任何一个。

现在，设 $X$ 是你删除了的元素中最大的一个，$Y$ 是最小的一个，请找出在最优情况下，$X-Y$ 的最小值。

输入格式

请从标准输入中读入：
$N$ $K$ $Q$
$A_1$ $A_2$ $...$ $A_N$

输出格式

请输出 $X-Y$ 可能的最小值。

限制

• $1\le K\le N\le 2000$
• $1\le Q\le N-K+1$
• $1\le A_i\le 10^9$
• 输入都是整数

5 3 2
4 3 1 5 2

1

10 1 6
1 1 2 3 5 8 13 21 34 55

7

11 7 5
24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784

451211184

提示

制約

• $1\ \leq\ N\ \leq\ 2000$
• $1\ \leq\ K\ \leq\ N$
• $1\ \leq\ Q\ \leq\ N-K+1$
• $1\ \leq\ A_i\ \leq\ 10^9$
• 入力はすべて整数である

Sample Explanation 1

$1$ 回目の操作では、どの長さ $3$ の連続する部分列を選んでも、そのうち最小の要素は $1$ です。 よって、$1$ 回目の操作によって $A_3=1$ が取り除かれ、$A=(4,3,5,2)$ となります。 $2$ 回目の操作では、連続する長さ $3$ の部分列として、$(A_2,A_3,A_4)=(3,5,2)$ を選び、$A_4=2$ を取り除くのが最適です。 この場合、取り除いた要素の最大値は $2$、最小値は $1$ になるので、その差は $2-1=1$ になります。