维护两个st表
#include<bits/stdc++.h>
using namespace std;
int n,q,a[50005],f1[50005][20],f2[50005][20];
int Log[50005];
void init(){
Log[1]=0;
for(int i=2;i<=n;i++) Log[i]=Log[i/2]+1;
for(int i=1;i<=n;i++){
f1[i][0]=a[i];
f2[i][0]=a[i];
}
for(int j=1;j<=Log[n];j++){
for(int i=1;i<=n;i++){
if(i+(1<<j)-1>n) break;
f1[i][j]=max(f1[i][j-1],f1[i+(1<<(j-1))][j-1]);
f2[i][j]=min(f2[i][j-1],f2[i+(1<<(j-1))][j-1]);
}
}
}
int ask(int l,int r){
int x=Log[r-l+1];
return max(f1[l][x],f1[r-(1<<x)+1][x])-min(f2[l][x],f2[r-(1<<x)+1][x]);
}
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
init();
for(int i=1;i<=q;i++){
int x,y;
cin>>x>>y;
cout<<ask(x,y)<<endl;
}
return 0;
}
