#include <iostream>
#include <algorithm>
using namespace std;
int maxn[50010][20];
int minn[50010][20];
int main()
{
    int t,n,q,x,y;
    cin>>n>>q;
    for(int c1=1;c1<=n;c1++)
    {
        cin>>t;//输入初始化在从c1开始长度为1的区间最大值最小值都为自己
        maxn[c1][0]=t;
        minn[c1][0]=t;
    }
    for(int c1=1;(1<<c1)<=n;c1++)//进行打表计算
        for(int c2=1;(c2+(1<<c1)-1)<=n;c2++)
        {
            maxn[c2][c1]=max(maxn[c2][c1-1],maxn[c2+(1<<(c1-1))][c1-1]);
            //2?c1的区间的最值为前2?c1-1区间的最值与后2?c1-1区间最值的最值
            minn[c2][c1]=min(minn[c2][c1-1],minn[c2+(1<<(c1-1))][c1-1]);
        }
    while(q--)
    {
        cin>>x>>y;
        int z=0;
        while(1<<(z+1)<=y-x+1)z++;
        //计算区间长度于2?z的关系
        int ans=max(maxn[x][z],maxn[y-(1<<z)+1][z])-min(minn[x][z],minn[y-(1<<z)+1][z]);
        cout<<ans<<endl;
    }
    return 0;
}