#include <stdio.h>
#include <stdlib.h>
#define Max 2000001
struct node 
{
    int x , y ;
}tree[Max];
int num[50001];
int n ,q ;
int min( int a , int b ) 
{
    if (a < b ) return a;
    return a;
}
int max( int a , int b )
{
   if (a > b ) return a ;
   return b;
}
void builtTree(int Node, int l , int r )
{
    if ( l == r )
    {
        tree[Node].x = tree[Node].y = num[l];
        return ;
    }
    int k = Node<<1;
    builtTree(k,l,(l+r)/2);
    builtTree(k+1,(l+r)/2+1,r);
    tree[Node].x=min(tree[k].x , tree[k+1].x);
    tree[Node].y=max(tree[k].y,tree[k+1].y);
}
int G_query_Max(int Node,int l , int r,int left,int right)
{
   if ( l == left &&  r == right )  return tree[Node].y;
   int mid = ( l + r ) /2 ;
   if ( left > mid ) return G_query_Max(Node*2+1,mid+1,r,left,right);
   else if ( right <= mid ) return G_query_Max(Node*2,l,mid,left,right);
      else  
      {
         int a = G_query_Max(Node*2,l,mid,left,mid);
         int b = G_query_Max(Node*2+1,mid+1,r,mid+1,right);
         return a > b ?a : b ;
      }
}
int G_query_Min(int Node,int l , int r,int left,int right)
{
   if ( l == left &&  r == right ) return tree[Node].x;
   int mid = ( l + r ) /2 ;
   if ( left > mid ) return G_query_Min(Node*2+1,mid+1,r,left,right);
   else if ( right <= mid ) return G_query_Min(Node*2,l,mid,left,right);
      else  
      {
         int a = G_query_Min(Node*2,l,mid,left,mid);
         int b = G_query_Min(Node*2+1,mid+1,r,mid+1,right);
         return a > b ?b : a ;
      }
}
int main()
{
     scanf("%d%d",&n,&q);
     int i;
     for ( i = 1 ; i <= n ; i ++ ) scanf("%d",&num[i]);
     builtTree(1,1,n);
     printf("%d\n",tree[1].y);
     for ( i = 1 ; i <= q ; i ++ )
     {
        int A,B;
        scanf("%d%d",&A,&B);
        printf("%d\n",G_query_Max(1,1,n,A,B)-G_query_Min(1,1,n,A,B));
     }
     //system("PAUSE");
    return 0;
}