#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 50005;
const int LOGN = 17;

int max_st[LOGN][MAXN];
int min_st[LOGN][MAXN];
int lg[MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    if (!(cin >> n >> q)) return 0;

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

    for (int i = 1; i <= n; ++i) {
        int h;
        cin >> h;
        max_st[0][i] = h;
        min_st[0][i] = h;
    }

    for (int j = 1; j < LOGN; ++j) {
        int len = 1 << (j - 1);
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            max_st[j][i] = max(max_st[j - 1][i], max_st[j - 1][i + len]);
            min_st[j][i] = min(min_st[j - 1][i], min_st[j - 1][i + len]);
        }
    }

    while (q--) {
        int a, b;
        cin >> a >> b;
        if (a > b) swap(a, b);
        int k = lg[b - a + 1];
        int mx = max(max_st[k][a], max_st[k][b - (1 << k) + 1]);
        int mn = min(min_st[k][a], min_st[k][b - (1 << k) + 1]);
        cout << mx - mn << "\n";
    }

    return 0;
}