#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

const int size = ;

int maxx[size][],minn[size][];

int n;

void init()

{

    int k = log2(n);

    for(int j = ;j <= k;j ++)

    {

        for(int i = ;i <= n;i ++)

        {

            maxx[i][j] = max(maxx[i][j-],maxx[i+(<<j-)][j-]);   //左边位运算优先级比较低,不用加括号

            minn[i][j] = min(minn[i][j-],minn[i+(<<j-)][j-]);   //这里[]内是[i+(1<<(j-1))],因为这个区间的另一部分是从上一部分末端开始。

        }

    }

}

int find(int l,int r)

{

    int k = log2(r-l+);

    int maxans = max(maxx[l][k],maxx[r-(<<k)+][k]);   //这两个区间可能有重复但是无关紧要，我要求的是最大和最小，就算重复也能求出最大和最小。

    int minans = min(minn[l][k],minn[r-(<<k)+][k]);   //同样，这个区间不会超过原区间的范围，因为分别从两个区间下手，考虑的最大化情况也是分别覆盖区间。

    return (maxans - minans);

}

int main()

{

    memset(minn,,sizeof(minn));

    int q;  scanf("%d%d",&n,&q);

    for(int i = ;i <= n;i ++)

    {

        scanf("%d",&maxx[i][]);

        minn[i][] = maxx[i][];

    }

    init();

    for(int i = ;i <= q;i ++)

    {

        int a,b;

        scanf("%d%d",&a,&b);

        int ans = find(a,b);

        printf("%d\n",ans);

    }

    return ;

}