#2 #8 #9 #10 WA

// Author:zymooll

#include<bits/stdc++.h>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define int long long
using namespace std;
int read(){
	int s=0,w=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')w=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=s*10+c-'0';
		c=getchar();
	}
	return s*w;
}
void print(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>=10)print(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=50000;
int n,q;
int l[MAXN];
int a[MAXN];
class ST_Base{
    private:
        int st[MAXN][18];
    public:
        virtual int cmp(int aa,int bb){return -1;}
        void init(){
            for(int i=1;i<=n;i++){
                st[i][0]=a[i];
            }
            for(int j=1;j<=l[n];j++){
                for(int i=1;i<=n-(1<<j)+1;i++){
                    st[i][j]=cmp(st[i][j-1],st[i+(1<<(j-1))][j-1]);
                }
            }
        }
        int ask(int L,int R){
            return cmp(st[L][l[R-L+1]],st[R-(1<<(l[R-L+1]))+1][l[R-L+1]]);
        }
};
class ST_MAX:public ST_Base{
    public:
        int cmp(int aa,int bb){
            return max(aa,bb);
        }
};
class ST_MIN:public ST_Base{
    public:
        int cmp(int aa,int bb){
            return min(aa,bb);
        }
};
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(),q=read();
    l[1]=0;
    l[2]=1;
    for(int i=3;i<=n;i++){
        l[i]=l[i>>1]+1;
    }
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    ST_MAX smax;
    ST_MIN smin;
    smax.init();
    smin.init();
    for(int i=1;i<=q;i++){
        int L=read(),R=read();
        print(smax.ask(L,R)-smin.ask(L,R));
        putchar('\n');
    }
	return 0;
}

Thanks!