rt，想出来一个疑似思维难度只有绿的解法。数据结构只用单调队列。
首先 O(qn3)O(qn^3)O(qn3) 做法很简单，做个前缀和就转化成了 Ar−Al−1A_r-A_{l-1}Ar −Al−1 。
O(qn2)O(qn^2)O(qn2) 也不难，画个图就知道了。
就是求每个段的最大值减去右边的数后取最大值就行，是一个滑动窗口，单调队列即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
考虑从右到左递推计算 iii。
我们会发现前面的 iii 就比后面的 iii 需要多更新几个数。
注意到每个 iii 的移动都只改变了最左边一个的，我们横过来看就会发现也是一个滑动窗口，单调队列即可。
O(nq)O(nq)O(nq)。由于 CCF 评测机非常快，也可以使用 ST 表代替单调队列。
如果这样是真的是不是这个可以降蓝了（
