#include<bits/stdc++.h>
using namespace std;
const int N = 50010;
int n, q;
int mx[N][24], mn[N][24], a[N];
void query(int l, int r)
{
    int x = log(r - l + 1) / log(2);
    int x1 = max(mx[l][x], mx[r - (1 << x) + 1][x]);
    int x2 = min(mn[l][x], mn[r - (1 << x) + 1][x]);
    printf("%d\n", x1 - x2);
}
int main()
{
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; ++i)
    {
        int x;
        scanf("%d", &a[i]);
        mx[i][0] = a[i];
        mn[i][0] = a[i];
    } 
    for(int i = 1; i <= 23; ++i)
        for(int j = n; j; --j) 
        {
            mn[j][i] = mn[j][i - 1];
            mx[j][i] = mx[j][i - 1];
            if(j + (1 << (i - 1)) <= n)
            {
                mx[j][i] = max(mx[j][i], mx[j + (1 << (i - 1))][i - 1]);
                mn[j][i] = min(mn[j][i], mn[j + (1 << (i - 1))][i - 1]);
            }
        }
    while(q--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        query(l, r);
    }    
    return 0;
}