Description

Loongint 要和 MM 结婚了。在两人的走进礼堂的红地毯两侧，需要摆一些装饰用的花篮，有一些不同高度的花篮，现在这些花篮被 Loongint 依照自己的美学观念编号为 S1, S2, S3, …, Sn，两侧的花篮高度一样。可 Loongint 的 MM 对这些花篮的摆放方式有不同的看法，她觉得满足以下条件的花篮摆放才是最好的。
如果对于区间 [Si, Sj] (1≤i<j≤n) 中任意的花篮都比 Si 低且比 Sj 低，那么这个区间称为一个美学区间。对于所有的美学区间，其长度（定义为 j−i）都必须小于等于 k，如果有长度大于 k 的美学区间，MM 就会不高兴，Loongint 就会有麻烦…

Input Format

第一行为 m。表示有 m 组测试数据。
对于每一组：
第一行 n, k，分别表示花篮的数量和美学区间的最大长度。
第二行为 n 个数，分别表示 S1, S2, S3, …, Sn 的值。

Output Format

如果根本不存在美学区间，输出 −1。
如果存在美学区间，那么如果任意区间的长度都小于等于 k，那么输出最大的长度，否则输出最大长度比 k 大多少（MaxLength-k）。

3
4 2
5 4 3 6
4 1
6 5 4 3
4 2
1 2 3 4

1
-1
1

Hint

对于 30% 的测试数据，1≤n≤100。
对于 60% 的测试数据，1≤n≤5,555。
对于 100% 的测试数据，1≤n≤100,000, 0<Si≤100,000, 1≤m≤3。

Source

数据结构 单调栈