#include<bits/stdc++.h>
using namespace std;
int n,q;
int logs2[50000];
int f[50000][17]; 
int f2[50000][17]; 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(f2,0x3f,sizeof(f2));
	cin >> n >> q;
	for(int i = 1;i<=n;i++){
		cin >> f[i][0];
		f2[i][0] = f[i][0];
	}
	for(int i = 2;i<=n;i++){
		logs2[i] = logs2[i/2]+1;
	}
	for(int i = 1;i<=16;i++){
		for(int j = 1;j+(1 << i)-1 <= n;j++){
			f[j][i] = max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
			f2[j][i] = min(f2[j][i-1],f2[j+(1<<(i-1))][i-1]);
		}
	}
	for(int i = 0;i<q;i++){
		int l,r;
		
		cin >> l >> r;
		int s = logs2[r-l+1];
		cout << max(f[l][s],f[r-(1<<s) + 1][s])-min(f2[l][s],f2[r-(1<<s) + 1][s]) << "\n";
	}
	return 0;
}