#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 5e4+10, M = 15;

int n, k;
int a[N];
int f[N][M], g[N][M];//f[i][j]表示以i为左端点,长度为2^j的子串中的最大值; g[i][j]则表示最小值

int log2(int n) {return log(n)/log(2);} //计算以2为底的对数

int maxl(int l, int r) { //询问区间最大值
    int k = r-l+1;
    return max(f[l][log2(k)], f[r-(1<<log2(k))+1][log2(k)]);
}

int minl(int l, int r) { //询问区间最小值
    int k = r-l+1;
    return min(g[l][log2(k)], g[r-(1<<log2(k))+1][log2(k)]);
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

    for (int j = 0; j <= log2(n); ++j) { //预处理
        for (int i = 1; i+(1<<j)-1 <= n; ++i) {
            if (j == 0) f[i][j] = a[i], g[i][j] = a[i];
            else f[i][j] = max(f[i][j-1], f[i+(1<<j-1)][j-1]), g[i][j] = min(g[i][j-1], g[i+(1<<j-1)][j-1]);
        }
    }

    while (k -- ) { //处理每次询问
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", maxl(l, r)-minl(l, r));
    }
    return 0;
}