本题的这个做法正确吗？思维难度是多少？

rt，想出来一个疑似思维难度只有绿的解法。数据结构只用单调队列。

首先 $O(qn^3)$ 做法很简单，做个前缀和就转化成了 $A_r-A_{l-1}$。

$O(qn^2)$ 也不难，画个图就知道了。

就是求每个段的最大值减去右边的数后取最大值就行，是一个滑动窗口，单调队列即可。

---

考虑从右到左递推计算 $i$。

我们会发现前面的 $i$ 就比后面的 $i$ 需要多更新几个数。

注意到每个 $i$ 的移动都只改变了最左边一个的，我们横过来看就会发现也是一个滑动窗口，单调队列即可。

$O(nq)$。由于 CCF 评测机非常快，也可以使用 ST 表代替单调队列。

如果这样是真的是不是这个可以降蓝了（