#include<bits/stdc++.h>
using namespace std;
int n, q, h[50010], log_2[50010], rmax[50010][10], rmin[50010][10];
int qmax(int a, int b) {
	int x = log_2[b - a + 1];
	return max(rmax[a][x], rmax[b - (1 << x) + 1][x]);
}
int qmin(int a, int b) {
	int x = log_2[b - a + 1];
	return min(rmin[a][x], rmin[b - (1 << x) + 1][x]);
}
signed main() {
	cin >> n >> q;
	for(int i = 1;i <= n;i ++) {
		cin >> h[i];
	}
	for(int i = 2;i <= n;i ++) {
		log_2[i] = log_2[i >> 1] + 1;
	}
	for(int i = 1;i <= n;i ++) {
		rmax[i][0] = h[i];
		rmin[i][0] = h[i];
	}
	for(int j = 1;(1 << j) <= n;j ++) {
		for(int i = 1;i <= n - (1 << j) + 1;i ++) {
			rmax[i][j] = max(rmax[i][j - 1], rmax[i + (1 << j - 1)][j - 1]);
			rmin[i][j] = min(rmin[i][j - 1], rmin[i + (1 << j - 1)][j - 1]);
		}
	}
	while(q --) {
		int A, B;
		cin >> A >> B;
		cout << qmax(A, B) - qmin(A, B) << endl;
	}
	return 0;
}