> #include <cstdio>
> #include <algorithm>
> using namespace std;
> int q,x,y,n,a[50005],f1[150005],f2[150005];
> void JZ (int i,int x,int y)
> {
>     if(x==y){f1[i]=a[x];f2[i]=a[x];return;}
>     int m=(x+y)/2;JZ (2*i,x,m);JZ (2*i+1,m+1,y);
>     f1[i]=max(f1[i*2],f1[i*2+1]);f2[i]=min(f2[i*2],f2[i*2+1]);
> }
> int CZ1 (int i,int x,int y,int q,int w)
> {
>     if(x>=q&&y<=w)return f1[i];
>     int m=(x+y)/2;
>     if(w<=m)return CZ1 (i*2,x,m,q,w);
>      else if(q>m)return CZ1 (i*2+1,m+1,y,q,w);
>       else return max(CZ1 (i*2,x,m,q,w),CZ1 (i*2+1,m+1,y,q,w));
> }
> int CZ2 (int i,int x,int y,int q,int w)
> {
>     if(x>=q&&y<=w)return f2[i];
>     int m=(x+y)/2;
>     if(w<=m)return CZ2 (i*2,x,m,q,w);
>      else if(q>m)return CZ2 (i*2+1,m+1,y,q,w);
>       else return min(CZ2 (i*2,x,m,q,w),CZ2 (i*2+1,m+1,y,q,w));
> }
> int main ()
> {
> 	scanf("%d%d",&n,&q);
>     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
>     JZ (1,1,n);
>     for(int i=1;i<=q;i++){
>         scanf("%d%d",&x,&y);
>         int m1=CZ1 (1,1,n,x,y);
>         int m2=CZ2 (1,1,n,x,y);
>         printf("%d\n",m1-m2);
>     }
> }