#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 500000
struct Node{
int left,right;
int max,min;
}tree[MAX];
int Min,Max;
void build(int root,int left,int right){
tree[root].left=left;
tree[root].right=right;
tree[root].max=0;
tree[root].min=9999999;
if(right-left==0) return;
int mid=(left+right)>>1;
build(2*root,left,mid);
build(2*root+1,mid+1,right);
}
void add(int root,int w,int h){
int lf=tree[root].left;
int rf=tree[root].right;
if(tree[root].max<h)
tree[root].max=h;
if(tree[root].min>h)
tree[root].min=h;
if(lf==rf) return;
int mid= (rf+lf)>>1;
if(w<=mid) add(2*root,w,h);
else add(2*root+1,w,h);
}
void query(int root,int left,int right){
int lf=tree[root].left;
int rf=tree[root].right;
if(lf==left&&rf==right){
if(tree[root].max>Max)
Max=tree[root].max;
if(tree[root].min<Min)
Min=tree[root].min;
return;
}
//if(lf==rf) return;
int mid=(lf+rf)>>1;
if(mid>=right)
query(2*root,left,right);
else if(mid<left)
query(2*root+1,left,right) ;
else
{query(2*root,left,mid);
query(2*root+1,mid+1,right);
}
}
int main(){
int n,m,i,j,high,left,right;
scanf("%d%d",&n,&m);
build(1,1,n);
/*for(i=1;i<=12;i++){
printf("%d %d %d %d",tree[i].left,tree[i].right,tree[i].min,tree[i].max);
system("pause");
}*/
for(i=1;i<=n;i++){
scanf("%d",&high);
add(1,i,high);
}
for(j=1;j<=m;j++){
scanf("%d%d",&left,&right);
Min=9999999;
Max=0;
query(1,left,right);
printf("%d\n",Max-Min);
// system("pause");
}
}
//不过还不会用ST算法。听说ST更好。继续学吧！