#pragma GCC optimize(3)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 50001;
int fmx[N][21], fmi[N][21];
int Log[N];
int n, m;
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &fmx[i][0]);
        fmi[i][0] = fmx[i][0];
    }

    Log[1] = 0;
    for (int i = 2; i < N; i++) {
        Log[i] = Log[i / 2] + 1;
    }

    for(int j = 1; j <= 20; j++)
        for(int i = 1; i + (1 << j) - 1 <= n; i++) {
            fmx[i][j] = max(fmx[i][j - 1], fmx[i + (1 << (j - 1))][j - 1]);
            fmi[i][j] = min(fmi[i][j - 1], fmi[i + (1 << (j - 1))][j - 1]);
    }

    while(m --) {
        int l, r;
        scanf("%d%d", &l, &r);
        int k = r - l + 1;
        // k = log2(k);
        k = Log[k];
        int mx = max(fmx[l][k], fmx[r - (1 << k) + 1][k]);
        int mi = min(fmi[l][k], fmi[r - (1 << k) + 1][k]);
        printf("%d\n", mx - mi);
    }

    return 0;
}