#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define Maxint 1073741824
int min(int a,int b)
{
    if(a>b)
        return b;
    return a;
}
int max(int a,int b)
{
    if(a<b)
        return b;
    return a;
}
int main()
{
    int n,q;
    scanf("%d",&n);
    scanf("%d",&q);
    int i,j,m=floor(log10((double)n)/log10(2.0));
    int data[n];
    for(i=0; i<n; i++)
        scanf("%d",&data[i]);
    int d[n][16];  //2^16=65536

    //init  1  min
    {
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
                d[i][j]=Maxint;
        }
        for(i=0; i<n; i++)
        {
            d[i][0]=data[i];
        }
        i=0;
        for(j=1; j<=m ; j++)
        {
            for(i=0; i<n; i++)
            {
                d[i][j]=d[i][j-1];
                if(i+(1<<(j-1))<n)
                    d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
               // printf("%d ",d[i][j]);
            }
          //  printf("\n");
        }
    }  //init 1 end
    int d2[n][16];
    {
        //init 2  max
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
                d2[i][j]=-Maxint;
        }
        for(i=0; i<n; i++)
        {
            d2[i][0]=data[i];
        }
        for(j=1; j<=m ; j++)
        {
            for(i=0; i<n; i++)
            {
                d2[i][j]=d2[i][j-1];
                if(i+(1<<(j-1))<n)
                  d2[i][j]=max(d2[i][j-1],d2[i+(1<<(j-1))][j-1]);
                //  printf("%d ",d2[i][j]);
            }
            // printf("\n");
        }
    }   //init 2 end

    int r,l,k,Min,Max;
    for(i=0; i<q; i++)
    {
        Min=Maxint;
        Max=-Maxint;
        scanf("%d %d",&l,&r);
        l--;
        r--;
        m=floor(log10((double)(r-l+1))/log10(2.0));
        Min=min(d[l][m],d[r-(1<<m)+1][m]);
        Max=max(d2[l][m],d2[r-(1<<m)+1][m]);

        printf("%d\n",Max-Min);
    }

    return 0;
}