#include <iostream>
#include<string>
#include<vector>
#include<cstring>
#include<cmath>
#include<queue>
#include<iomanip>
using namespace std;

int n;


int main(){
    int cnt=0;
    cin>>n;
    int two[n+1];
    memset(two,-1,sizeof(two));
    for(int i=1;i<=n;i=i*2){
         two[i]=cnt;cnt++;
    }
    cnt--;
    vector <int> a[n+1];
    vector <int>b[n+1];
    int q;
    cin>>q;
    int dd;
    for(int i=1;i<=n;i++) {
        cin>>dd;
        a[i].push_back(dd);
        b[i].push_back(dd);
    }
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=n-(1<<i)+1;j++){
            int aa=min(a[j][i-1],a[j+(1<<(i-1))][i-1]);
            a[j].push_back(aa);
            int bb=max(b[j][i-1],b[j+(1<<(i-1))][i-1]);
            b[j].push_back(bb);
        }
    }
    int x,y;
    while(q--){
        cin>>x>>y;
        int d=y-x+1;
        int s=0;
        int p=d;
        int m=0;
        int n=a[x][0];
        int st=x;
        while(d!=0){
            if(two[p]!=-1){
                m=max(m,b[st][two[p]]);
                n=min(n,a[st][two[p]]);
                st=st+p;
                d=d-p;
                p=s;
            }
            else{
                p--;
                s++;
            }
        }
        cout<<m-n<<endl;
    }
}