#include <cstdio>

 #include <math.h>

 #define max(a,b) ((a>b)?a:b)

 #define min(a,b) (a<b?a:b)

 const int maxn=;

 int h[maxn];

 int mx[maxn][],mn[maxn][];

 int n,q;

 void rmq_init(){

     int i,j,t;

     for(j=;j<=n;j++) mx[j][]=mn[j][]=h[j];

     int m=floor(log((double)n)/log(2.0));

     for(i=;i<=m;i++){

         for(j=;j<=n;j++){

             t = j+(<<(i-));

             if(t<=n) mx[j][i]=max(mx[j][i-],mx[t][i-]);

             else mx[j][i]=mx[j][i-];

         }

     }

     for(i=;i<=m;i++){

         for(j=;j<=n;j++){

             t = j+(<<(i-));

             if(t<=n) mn[j][i]=min(mn[j][i-],mn[t][i-]);

             else mn[j][i]=mn[j][i-];

         }

     }

 }

 int rmq(int l,int r){

     int m=floor(log((double)(r-l+))/log(2.0));

     int a=max(mx[l][m],mx[r-(<<m)+][m]);

     int b=min(mn[l][m],mn[r-(<<m)+][m]);

     return a-b;

 }

 int main(){

     int i,l,r;

     int T,C,L,R;

     scanf("%d%d",&n,&q);

     for(i = ;i <= n;i++)

         scanf("%d",&h[i]);

     rmq_init();

     while(q--){

         scanf("%d%d",&L,&R);

         printf("%d\n",rmq(L,R));

     }

     return ;

 }