问题描述

给定一个长度为$N$的整数序列$A$和一个整数$K$。你将对这个序列执行以下操作$Q$次：

• 选择一个长度为$K$的连续子序列，然后移除其中包含的$K$个元素中最小的元素（如果有多个这样的元素，任选一个）。

设$X$和$Y$分别为执行$Q$次操作后移除的最大和最小元素的值。你希望$X-Y$尽可能小。找出当操作进行得最优时，$X-Y$的最小值。

约束条件

• $1 \leq N \leq 2000$
• $1 \leq K \leq N$
• $1 \leq Q \leq N-K+1$
• $1 \leq A_i \leq 10^9$
• 输入中的所有值都是整数。

输入

输入是标准输入提供的，格式如下：

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

输出

打印$X-Y$的最小可能值。

示例输入 1

5 3 2
4 3 1 5 2

示例输出 1

1

在第一次操作中，无论我们选择哪个长度为$3$的连续子序列，其中的最小元素都是$1$。因此，第一次操作移除了$A_3=1$，现在我们有$A=(4,3,5,2)$。在第二次操作中，最优的选择是选择长度为$3$的连续子序列$(A_2,A_3,A_4)=(3,5,2)$并移除$A_4=2$。这种情况下，最大和最小被移除的元素分别为$2$和$1$，它们的差值为$2-1=1$。

示例输入 2

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

示例输出 2

7

示例输入 3

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

示例输出 3

451211184