#include <bits/stdc++.h>
using namespace std;
const int N = 50001;
int inter[2][N], arr[N];
int n, q, l, r;
int ls(int indx) {
return indx & (-indx);
}
void update(int indx, int val) {
int mx = val, mn = val;
for (; indx <= n; indx += ls(indx)) {
inter[1][indx] = mx = max(mx, inter[1][indx]);
inter[0][indx] = mn = min(mn, inter[0][indx]);
}
}
int get(int l, int r) {
int mx = 0, mn = 1e9;
while (r >= l) {
while (r - ls(r) < l && r >= l) {
mx = max(mx, arr[r]);
mn = min(mn, arr[r]);
--r;
}
if (r >= l)
mx = max(mx, inter[1][r]), mn = min(mn, inter[0][r]);
r -= ls(r);
}
return mx - mn;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("a.in", "r", stdin);
#endif
scanf("%d %d", &n, &q);
memset(inter[0], 127, sizeof(int) * (n + 1));
for (int i = 1; i <= n; ++i)
scanf("%d", &arr[i]), update(i, arr[i]);
while (q--) {
scanf("%d %d", &l, &r);
if (l == r) {
puts("0");
continue;
}
printf("%d\n", get(l, r));
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNvbnN0IGludCBOID0gNTAwMDE7CmludCBpbnRlclsyXVtOXSwgYXJyW05dOwppbnQgbiwgcSwgbCwgcjsKaW50IGxzKGludCBpbmR4KSB7CglyZXR1cm4gaW5keCAmICgtaW5keCk7Cn0Kdm9pZCB1cGRhdGUoaW50IGluZHgsIGludCB2YWwpIHsKCWludCBteCA9IHZhbCwgbW4gPSB2YWw7Cglmb3IgKDsgaW5keCA8PSBuOyBpbmR4ICs9IGxzKGluZHgpKSB7CgkJaW50ZXJbMV1baW5keF0gPSBteCA9IG1heChteCwgaW50ZXJbMV1baW5keF0pOwoJCWludGVyWzBdW2luZHhdID0gbW4gPSBtaW4obW4sIGludGVyWzBdW2luZHhdKTsKCX0KfQppbnQgZ2V0KGludCBsLCBpbnQgcikgewoJaW50IG14ID0gMCwgbW4gPSAxZTk7Cgl3aGlsZSAociA+PSBsKSB7CgkJd2hpbGUgKHIgLSBscyhyKSA8IGwgJiYgciA+PSBsKSB7CgkJCW14ID0gbWF4KG14LCBhcnJbcl0pOwoJCQltbiA9IG1pbihtbiwgYXJyW3JdKTsKCQkJLS1yOwoJCX0KCQlpZiAociA+PSBsKQoJCQlteCA9IG1heChteCwgaW50ZXJbMV1bcl0pLCBtbiA9IG1pbihtbiwgaW50ZXJbMF1bcl0pOwoJCXIgLT0gbHMocik7Cgl9CglyZXR1cm4gbXggLSBtbjsKfQppbnQgbWFpbigpIHsKI2lmbmRlZiBPTkxJTkVfSlVER0UKCWZyZW9wZW4oImEuaW4iLCAiciIsIHN0ZGluKTsKI2VuZGlmCglzY2FuZigiJWQgJWQiLCAmbiwgJnEpOwoJbWVtc2V0KGludGVyWzBdLCAxMjcsIHNpemVvZihpbnQpICogKG4gKyAxKSk7Cglmb3IgKGludCBpID0gMTsgaSA8PSBuOyArK2kpCgkJc2NhbmYoIiVkIiwgJmFycltpXSksIHVwZGF0ZShpLCBhcnJbaV0pOwoJd2hpbGUgKHEtLSkgewoJCXNjYW5mKCIlZCAlZCIsICZsLCAmcik7CgkJaWYgKGwgPT0gcikgewoJCQlwdXRzKCIwIik7CgkJCWNvbnRpbnVlOwoJCX0KCQlwcmludGYoIiVkXG4iLCBnZXQobCwgcikpOwoJfQoJcmV0dXJuIDA7Cn0K