#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#define INF 0x3f3f3f
#define MAX 50005
using namespace std;
int lowbit[50005],build_min[50005],build_max[50005],n,a[50005];
void GetLow()
{
    for(int i = 1; i <= n; i++)
        lowbit[i] = i&(-i);
}
void TreeBuild()
{
    for(int i = 1; i <= n; i++)
    {
        build_max[i] = 0;
        build_min[i] = 9999999;
        for(int j = i; j > i-lowbit[i]; j--)
        {
            build_max[i] = max(build_max[i],a[j]);
            build_min[i] = min(build_min[i],a[j]);
        }
    }
}
int query_max(int x,int y)
{
    int ans = a[y];
    while(y != x)
    {
        for(y -= 1; y - lowbit[y] > x; y -= lowbit[y])
            ans = max(ans,build_max[y]);
        ans = max(ans,a[y]);
    }
    return ans;
}
int query_min(int x,int y)
{
    int ans = a[y];
    while(y != x)
    {
        for(y -= 1; y - lowbit[y] > x; y -= lowbit[y])
            ans = min(ans,build_max[y]);
        ans = min(ans,a[y]);
    }
    return ans;
}
int main()
{
    int m;
    while(~scanf("%d%d",&n,&m))
    {
        GetLow();
        for(int i = 1; i <= n; i++)
            scanf("%d",&a[i]);
        TreeBuild();
        while(m--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(a == b) cout << 0 << endl;
            else
                cout <<  query_max(a,b) - query_min(a,b) << endl;
        }
    }
}