自用RMQ，状态转移方程如下：

ma[i][j]=max(ma[i][j-1],ma[i+(1<<j)][j-1]);

mi[i][j]=min(mi[i][j-1],mi[i+(1<<j)][j-1]);

#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
int n,q,r1[50005][20],r2[50005][20];
int getAns(int l,int r){
	int x=(int)(log2(r-l+1));
	return max(r1[l][x],r1[r-(1<<x)+1][x])-min(r2[l][x],r2[r-(1<<x)+1][x]);
}
int main(){
	scanf("%d%d",&n,&q);
	for(int j=1;(1<<j)<=n;j++) for(int i=1;i<=n;i++) r2[i][j]=1e8;
	for(int i=1;i<=n;i++) scanf("%d",&r1[i][0]),r2[i][0]=r1[i][0];
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i<=n;i++)
			r1[i][j]=max(r1[i][j-1],r1[i+(1<<(j-1))][j-1]);
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i<=n;i++)
			r2[i][j]=min(r2[i][j-1],r2[i+(1<<(j-1))][j-1]);
	while (q--){
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",getAns(l,r));
	}
	return 0;
}