最小极差

题目描述

小 A 有一个长度为 $n$ 的正整数序列 $a$ ，他定义这个序列的权值为所有长度为 $k$ 的区间的最小极差，即：

$$\min_{l=1}^{n-k+1}\left\{\max_{i=l}^{l+k-1}a_i-\min_{i=l}^{l+k-1}a_i\right\}$$

小 A 可以进行至多 $m$ 次操作：每次操作选择一个满足 $1\le l\le r\le n$ 的区间 $[l,r]$ ，将 $[l,r]$ 这段区间翻转，也就是变为 $a_r,a_{r-1},\cdots,a_l$ 。

小 A 想求出在进行不超过 $m$ 次翻转操作后，所有可能得到的序列中权值的最小值。

第一行包含一个整数 $t$ （ $1\le t\le 50000$ ），表示测试数据组数。接下来有 $t$ 组测试数据。每组测试数据格式如下：

第一行输入三个整数 $n,m,k$ （ $1\le n\le 2\times10^5$ ， $0\le m\le n$ ， $1\le k\le n$ ），表示序列长度、操作次数与区间长度。

第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$ （ $1\le a_i\le 10^9$ ），表示序列 $a$ 。

所有测试数据中 $n$ 的总和不超过 $2\times 10^5$ 。

对于每组测试数据，输出一行一个整数，表示进行操作后序列 $a$ 的最小权值。

3
6 0 3
1 6 5 9 7 12
6 1 3
1 6 5 9 7 12
10 2 5
8 6 1 7 3 12 15 5 1 9

4
2
5