#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int block_min[250];
int block_max[250];
int a[50010];
int main() {
    int n, q, k;
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    k = (int)sqrt((long double)n);  
    
    memset(block_min, 0x7f, sizeof(block_min));
    for (int i = 0; i < n; i++) {
        block_max[i / k] = max(block_max[i / k], a[i]);
        block_min[i / k] = min(block_min[i / k], a[i]);
    }

    for (int i = 0; i < q; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        l--;
        r--;
        int _min = 0x7fffffff;
        int _max = 0;
        for (int j = l; j <= r;) {
            if (j % k == 0 && j + k <= r) {
                _max = max(_max, block_max[j / k]);
                _min = min(_min, block_min[j / k]);
                j += k;
            } else {
                _max = max(_max, a[j]);
                _min = min(_min, a[j]);
                j++;
            }
        }
        printf("%d\n", _max - _min);
    }
    return 0;
}