#include<iostream>
#include<stdio.h>
#include<math.h>
#define MAX(a,b) a>b?a:b;
#define MIN(a,b) a<b?a:b;
using namespace std;
int n,q;
int num[50010];
int f_max[50010][20],f_min[50010][20];
int init_rmq()
{
     for(int i=0;i<n;i++)
     {
         f_max[i][0]=num[i];
         f_min[i][0]=num[i];
     }
     for(int j=1;j<=(int)(log(n)/log(2));j++)
     {
         for(int i=0;i<=(int)(n-(1<<j));i++)
         {
             f_max[i][j]=MAX(f_max[i][j-1],f_max[i+(1<<j-1)][j-1]);
             f_min[i][j]=MIN(f_min[i][j-1],f_min[i+(1<<j-1)][j-1]);
         }
     }
}
int main()
{
     while(scanf("%d%d",&n,&q)!=EOF)
     {
         int l,r;
         for(int i=0;i<n;i++)
         {
             scanf("%d",&num[i]);
         }
         init_rmq();
         for(int i=0;i<q;i++)
         {
             scanf("%d%d",&l,&r);
             int x=(int)(log(r-l+1)/log(2));
             int r1=MAX(f_max[l-1][x],f_max[r-1-(1<<x)+1][x])
             int r2=MIN(f_min[l-1][x],f_min[r-1-(1<<x)+1][x]);
             printf("%d\n",r1-r2);
         }
     }
    
}