这种题第一眼看上去不可做，我们考虑证明一个结论：
对于一个区间的 \(Lipschitz\) 常数 \(k\) ,应满足：
\[k=\max_{i=l}^{r-1} \left\{\frac{a[i+1]-a[i]}{i+1-i}\right\}
\]
即
\[k=\max_{i=l}^{r-1} \left\{|a[i+1]-a[i]|\right\}
\]
证明：
考虑三个数的情况，设它们分别是：\(\left\{0,x,\infty\right\}\)
那么，相邻的区间的 \(Lipschitz\) 常数 \(k=\left\{x,\infty-x\right\}\)
而整体区间的 \(Lipschitz\) 常数 \(k=\frac{\infty}{2}\)
那么考虑 \(x\) 的取值会发现，无论 \(x\) 怎么取值，相邻区间的 \(Lipschitz\) 常数 \(k\) 必然要大于整体区间的 \(k.\) 而根据三个数的区间进行推广即可。
证毕。
那么我们接下来的任务就是回答询问了，观察到询问数目很少，所以我们用 \(O(nq)\) 的复杂度就可以了。
考虑如何 \(O(n)\) 回答一组询问：
观察相邻区间的 \(k\) 会出现多少次。我们求出左边和右边第一个大于它的数的位置，那么在这个区间中，任意一个包含它的区间都会让 \(k\) 出现一次。那么如果我们可以 \(O(n)\) 求出这个东西，问题就解决了。
显然单调栈可以完成这个任务。
于是这题做完了。单调栈内部维护数值递减的序列下标，每次弹出栈的时候更新栈顶元素的目标值就好了。
总复杂度：\(O(nq).\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=2e5+10;
const int inf=(1<<30);
int n,q,a[MAXN],h[MAXN];
inline int Abs(int x){if(x<0)return -x;return x;}
int st[MAXN],top;
int l[MAXN],r[MAXN];
signed main(){
scanf("%lld%lld",&n,&q);
for(int i=1;i<=n;++i)scanf("%lld",&h[i]);
for(int i=1;i<n;++i)a[i]=Abs(h[i+1]-h[i]);
for(;q;q--){
int L,R;
scanf("%lld%lld",&L,&R);
R--;
memset(l,0,sizeof l);
memset(r,0,sizeof r);
int ans=0;
for(int i=L,j=1;i<=R;++i,++j)a[j]=Abs(h[i+1]-h[i]);
int len=R-L+1;
top=0;
for(int i=1;i<=len;++i){
while(top&&a[st[top]]<a[i]){
r[st[top]]=i-st[top];
top--;
}
l[i]=i-st[top];
st[++top]=i;
}
while(top)r[st[top]]=len+1-st[top],top--;
for(int i=1;i<=len;++i)ans+=a[i]*l[i]*r[i];
printf("%lld\n",ans);
}
return 0;
}