#include<cstdio>
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
long long a[1000005];
long long mi[1000005];
long long ma[1000005]; 
inline long long lchild(long long cnt){
   return (cnt << 1);
}

inline long long rchild(long long cnt){
    return (cnt << 1) + 1;
}

void push_up(long long p){
    mi[p] = min(mi[lchild(p)], mi[rchild(p)]);
    ma[p] = max(ma[lchild(p)], ma[rchild(p)]); 
}

void build_tree(long long p, long long l, long long r){
    if(l == r){
    	mi[p] = a[l];
    	ma[p] = a[l];
    	return;
    }
	long long mid = (l + r) >> 1;
	build_tree(lchild(p), l, mid);
	build_tree(rchild(p), mid + 1, r);
	push_up(p);
}

long long que_min(long long p, long long l, long long r, long long ql, long long qr){
//	cout << p << endl;
    if(l >= ql && r <= qr){
        return mi[p];
	}
	long long mid = (l + r) / 2;
	long long ans = 1e9;
	if(ql <= mid){
	    ans = min(ans, que_min(lchild(p), l, mid, ql, qr));
	}
	if(qr > mid){
	    ans = min(ans, que_min(rchild(p), mid + 1, r, ql, qr));
	}
	return ans;
}

long long que_max(long long p, long long l, long long r, long long ql, long long qr){
    if(l >= ql && r <= qr){
        return ma[p];
	}
	long long mid = (l + r) / 2;
	long long ans = -1e9;
	if(ql <= mid){
	    ans = max(ans, que_max(lchild(p), l, mid, ql, qr));
	}
	if(qr > mid){
	    ans = max(ans, que_max(rchild(p), r, mid, ql, qr));
	}
	return ans;
}

int main(){
    long long n, m;
    cin >> n >> m;
    for(long long i = 1; i <= n; i++){
        cin >> a[i];
	}
	build_tree(1, 1, n);
	for(long long i = 0; i < m; i++){
		long long a, b;
		cin >> a >> b; 
		long long tmax = que_max(1, 1, n, a, b);
		long long tmin = que_min(1, 1, n, a, b);
	    cout << tmax - tmin << endl;
	}
    return 0;
}