代码如下：

#include<bits/stdc++.h>

using namespace std;

struct qwe{

	int maxn,minn;
    
}a[50010][250];

int main(){

	std::ios::sync_with_stdio(0);
    
	std::cin.tie(nullptr);
    
	std::cout.tie(nullptr);
    
	int n,b;
    
	cin>>n>>b;int c;
    
	for(int i=1;i<=n;i++){
    
		cin>>c;
        
		a[i][1].maxn=c;
        
		a[i][1].minn=c;
        
	}
    
	for(int i=2;(1<<i-1)-1<=n;i++){
    
		for(int j=1;j+(1<<i-1)-1<=n;j++){
        
			a[j][i].maxn=max(a[j][i-1].maxn,a[j+(1<<i-2)][i-1].maxn);
            
			a[j][i].minn=min(a[j][i-1].minn,a[j+(1<<i-2)][i-1].minn);
            
		} 
        
	}
    
	int l,r;
    
	for(int i=0;i<b;i++){
    
		cin>>l>>r;
        
		int t=int(sqrt(r-l+1));
        
		if(sqrt(r-l+1)!=t)t++;
        
		int u=max(a[l][t].maxn,a[r-(1<<t-1)+1][t].maxn);
        
		int y=min(a[l][t].minn,a[r-(1<<t-1)+1][t].minn);
        
		cout<<u-y<<endl;
	}
	
	return 0;
}