TT 猫咖的生意越来越红火，人越来越多，也越来越拥挤。
为了解决这个问题，TT 决定扩大营业规模，但猫从哪里来呢？
TT 第一时间想到了神秘人，想要再次通过完成任务的方式获得猫咪。
而这一次，神秘人决定加大难度。
给定一个环，A[1], A[2], A[3], … , A[n]，其中 A[1] 的左边是 A[n]。要求从环上找出一段长度不超过 K 的连续序列，使其和最大。
这一次，TT 陷入了沉思，他需要你们的帮助。
第一行一个整数 T，表示数据组数，不超过 100。
每组数据第一行给定两个整数 N K。（1 ≤ N ≤ 100000, 1 ≤ K ≤ N）
接下来一行，给出 N 个整数。（-1000 ≤ A[i] ≤ 1000）。
对于每一组数据，输出满足条件的最大连续和以及起始位置和终止位置。
如果有多个结果，输出起始位置最小的，如果还是有多组结果，输出长度最短的。
4 6 3 6 -1 2 -6 5 -5 6 4 6 -1 2 -6 5 -5 6 3 -1 2 -6 5 -5 6 6 6 -1 -1 -1 -1 -1 -1
7 1 3 7 1 3 7 6 2 -1 1 1
这是一道典型的单调队列优化DP问题。
1. 什么是单调队列优化DP？
回顾一下单调队列👉[week5]滑动窗口——单调双向队列（线性结构的应用）
在动态规划过程当中，利用单调队列对动态规划进行优化的方式就是单调队列优化DP。
这一类的问题往往具有比较明显的特征。状态转移方程当中需要用到一个最值，而这个最值是从序列当中抽取一定长度的连续子序列中得到的。显然这个最值的求解就是滑动窗口问题，也就是单调队列的经典问题。所以，在过程中用单调队列对该最值进行维护，就能达到在动态规划求解过程中优化时间复杂度的目的。
2. 经典题型
最大连续子段和 这个问题的关键在于多了一个对于子序列的长度限制。这个长度限制显然就是滑动窗口的大小。（1）定状态
（2）状态转移方程
通过转移方程可以发现，其中的被减数就是可以由单调队列维护的滑动窗口来求解的最值。也就是在一段连续的规定子段中找出最值，此处是最小值。
以第i个元素为结尾的最大连续子段和一定等于第i个前缀和减去它前面k个前缀和中的最小值。
第一，第i个前缀和与其前面k个前缀和的差值都是长度不大于k的连续子段和，都是合法的。 第二，第i个前缀和是固定不变的。要想连续子段和最大，就说明减数需要越小。也就是说需要得到前k个前缀和中的最小值。（3）代码模版
在这种做法中，所有元素从第1个算起。
❗️问题：
最大值为负数时需要注意的是，这个模版只适用于最大值一定为正数的情况。因为ans的初始化为0。 如果一个序列中的最大值为负数，则其中计算所得的所有结果都比初始结果小，因此无法正常进行动态规划。
（4）前缀和
为了进一步优化时间复杂度，在这种题型的解题过程中使用的并不是原序列，而是序列的前缀和。
前缀和其实是原序列的一种存储方式。
一般我们在数组中是依次存储对应第i个位置上的元素，而在前缀和中，我们存储的是前i个元素的和:
sum[i] = a[0] + a[1] + ... a[i]因此显然，第i个和第j个前缀和的差即为第i + 1个元素到第j个元素的和(j > i):
sum[i] - sum[j] = a[0] + a[1] + ...+a[i + 1] + ... + a[j] - (a[0] + a[1] + ... a[i]) = a[i + 1] + a[i + 2] ... a[j]而第i个元素也可以通过第i个前缀和减去第i-1个前缀和得到：
sum[i] - sum[i - 1] = a[i]这道题就是典型的最大连续子段和问题，但是这道题不同的地方有三个：
环形序列 存在最大值为负数的情况 需要记录选择子段的起始针对这三个不同要进行改写：
1. 环形序列
环形序列与单向序列的不同就在于：环形序列没有结尾。
也就是说当环形序列从第一个走到最后一个后，仍然可以继续前进。也就是从最后一个再次回到第一个重新开始。
对于这种结构的处理方式就是：切环为链
将该序列按单向顺序在数组中两次存放。也就是先存放一个序列，然后再接着该序列再次存放一个同样的序列。显然如果从起始顺序向后遍历，当遍历到第二个序列的最后时，就相当于完成了对环形序列的两次遍历。也就实现了头尾相连。
在这道题中，对一条选择的子段有最大长度的限制k。也就是说如果选择的一个序列起始为最后一个元素，那么最远的结尾元素也只可能是第k - 1个元素。
所以在这道题中在第一个序列后再多存储前k - 1个元素就足够了。
2. 最大值为负数
在前面已经提到过这个问题。只需要将ans初始化为所选数据类型的最小值即可。
在这道题中通过估算可以发现int类型足以表示所有结果。因此将ans初始化为int最小值即可。
3. 需要记录选择子段的起始
在这道题中，如果按照模版来做，可能出现由于前缀和都小于最开始压入队列中的0而全部被弹出，导致结果错误的情况。
除此之外，如果记录的所有起点都是减去前缀和的序号 + 1。那么队列中剩下的只有当前压入的第i个前缀和，则最后得到的差为0，且对应的起点+1后会出现大于终点的不合法情况。无法得到起始相同，也就是只选择某一个元素的情况。
因此我们需要修改一下这个模版：
若不改变起始的记录方法，也就是当ans被更新时，起始点记录为当前队列首元素记录的序号+1。那么也就代表着如果存在只选择一个元素时，队列首元素只能是该元素的序号-1。
那么，在以第i个元素为结尾求解时，压入的元素应该是其前一个元素。这样的话就能保证所有得到的情况都是合法，并且能得到所有情况。
这样做了修改之后，就不需要在最开始提前压入第0个前缀和。第0个前缀和本来的目的就是为了保证选择一个元素的情况不被忽略。
需要注意的是，由于将环形化作了链状，因此在最后一个元素之后添加的元素实际的序号应该要减去n。
