#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,q;
int dmin[50005][50];
int dmax[50005][50];
int a[1000000];
int ansmin, ansmax;
void RMQ_ini()
{
for(int i = 0; i < n; i++)
dmin[i][0] = dmax[i][0] = a[i];
for(int j = 1; (1<<j) <= n; j++)
for(int i = 0; i + (1<<j) - 1 < n; i++)
{
dmin[i][j] = min(dmin[i][j-1], dmin[i+(1<<(j-1))][j-1]);
dmax[i][j] = max(dmax[i][j-1], dmax[i+(1<<(j-1))][j-1]);
}
}
void RMQ(int L, int R)
{
int k = 0;
while((1 << (k+1)) <= R-L+1) k++;
ansmin = min(dmin[L][k], dmin[R-(1<<k)+1][k]);
ansmax = max(dmax[L][k], dmax[R-(1<<k)+1][k]);
}
int main()
{
//freopen("ztest.txt","r",stdin);
while(scanf("%d%d",&n,&q) == 2)
{
memset(dmin,0,sizeof(dmin));
memset(dmax,0,sizeof(dmax));
for(int i = 0; i < n; i++)
scanf("%d",&a[i]);
RMQ_ini();
for(int i = 1; i <= q; i++)
{
int l,r;
scanf("%d%d",&l,&r);
RMQ(l-1,r-1);
//printf("%d %d\n",ansmax, ansmin);
printf("%d\n",ansmax-ansmin);
}
}
return 0;
}
