AT_arc098_c [ARC098E] Range Minimum Queries

你有一个长度为 $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$ - 输入都是整数

### 制約 - $ 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 $ になります。