#include<bits/stdc++.h>
using namespace std;
const int N=50010;
int maxx[N][30],minn[N][30];
int h[N];
int n,q;
void init()
{
    for(int j=0;j<30;j++)
       for(int i=1;i+(1<<j)-1<=n;i++)
           if(!j){maxx[i][j]=h[i];minn[i][j]=h[i];}
           else 
           {
               maxx[i][j]=max(maxx[i][j-1],maxx[i+(1<<j-1)][j-1]);
               minn[i][j]=min(minn[i][j-1],minn[i+(1<<j-1)][j-1]);
           }
}
int query(int l,int r)
{
    int len=r-l+1;
    int k=log2(len);
    return max(maxx[l][k],maxx[r-(1<<k)+1][k])-min(minn[l][k],minn[r-(1<<k)+1][k]);
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>h[i];
    init();
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        cout<<query(l,r)<<endl;
    }
    return 0;
}