[USACO07JAN]平衡的阵容Balanced Lineup

#include<cstdio>
#include<cctype>
using namespace std;
#define C c=getchar()
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
inline int readint(){
	char C;
	bool b=false;
	while(!isdigit(c))b=c=='-',C;
	int p=0;
	while(isdigit(c))p=((p<<3)+(p<<1)+(c^'0')),C;
	return (b)?-p:p;
}
int n,q,L,R,Ansmin,Ansmax;
int Max[300005],Min[300005];
void bt(int l,int r,int o){
	if(l==r){
		Max[o]=Min[o]=readint();
		return;
	}
	int mid=l+r>>1;
	bt(l,mid,o<<1);
	bt(mid+1,r,o<<1|1);
	Max[o]=max(Max[o<<1],Max[o<<1|1]);
	Min[o]=min(Min[o<<1],Min[o<<1|1]);
}
void query(int l,int r,int o){
	if(L<=l&&r<=R){
		Ansmax=max(Ansmax,Max[o]);
		Ansmin=min(Ansmin,Min[o]);
		return;
	}
	int mid=l+r>>1;
	if(L<=mid)query(l,mid,o<<1);
	if(mid<R)query(mid+1,r,o<<1|1);
}
int main(){
	n=readint(),q=readint();
	bt(1,n,1);
	while(q--){
		L=readint(),R=readint();
		Ansmin=100000000;
		Ansmax=-Ansmin;
		query(1,n,1);
		printf("%d
",Ansmax-Ansmin);
	}
	return 0;
}