/*******************线段树*******************************/
#include<iostream>
using namespace std;
int height[50001];
int n,q;
int a,b;
struct seg
{
    int l,r;
    int large,small;
}s[1000000];
int ll,ss;
int min(int a,int b)
{
    return a>b?b:a;
}
int max(int a,int b)
{
    return a>b?a:b;
}
int build(int a,int b,int t)
{
    
    s[t].l=a;
    s[t].r=b;
    if(a==b)
    {   
        s[t].large=height[a];
        s[t].small=height[a];
        return 0;
    }
    else
    {
        int mid=(a+b)/2;
        build(a,mid,2*t);
        build(mid+1,b,2*t+1);
        s[t].large=max(s[2*t].large,s[2*t+1].large);
        s[t].small=min(s[2*t].small,s[2*t+1].small);
    }
    return 0;
}
int check(int a,int b,int step)
{
    if(s[step].l==a&&s[step].r==b)
    {
        if(s[step].large>ll)
            ll=s[step].large;
        if(s[step].small<ss)
            ss=s[step].small;
        return 0;
    }
    else
    {
        int mid=(s[step].l+s[step].r)>>1;
        if(mid>=b)
        {
            check(a,b,2*step);
        }
        else if(mid<a)
        {
            check(a,b,2*step+1);
        }
        else
        {
            check(a,mid,2*step);
            check(mid+1,b,2*step+1);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    int i,j;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&height[i]);
    }
    build(1,n,1);
    for(j=1;j<=q;j++)
    {
        scanf("%d%d",&a,&b);
        ll=0;ss=10000000;
        check(a,b,1);
        printf("%d\n",ll-ss);
    }
    system("pause");
    return 0;
}
/***************************************rmq***************************/
 
#include<iostream>
#include<cmath>
using namespace std;
int a[50001],Q1,Q2,n,Q,dp1[50001][20],dp2[50001][20];
int main()
{
	int i,j;
	scanf("%d%d",&n,&Q);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		dp1[i][0]=a[i];
		dp2[i][0]=a[i];
	}
	for(j=1;j<=int(log((double)n)/log(2.0));j++)
	{
		for(i=1;i+(1<<j)-1<=n;i++)
		{
			dp1[i][j]=min(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);
			dp2[i][j]=max(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);
		}
	}
	while(Q--)
	{
		scanf("%d%d",&Q1,&Q2);
		int k=(int)(log((double)(Q2-Q1+1))/log(2.0));
		printf("%d\n",max(dp2[Q1][k],dp2[Q2-(1<<k)+1][k])-min(dp1[Q1][k],dp1[Q2-(1<<k)+1][k]));
	}
	system("pause");
	return 0;
}