var n,i,j,q,f,t,times:longint;

 hmin,hmax:array[..,..] of longint;

 function min(a,b:longint):longint;

 begin

   if a>b then exit(b)

     else exit(a);

 end;

 function max(a,b:longint):longint;

 begin

   if a>b then exit(a)

     else exit(b);

 end;

 begin

   readln(n,q);

   for i:= to n do

     begin

       readln(hmax[,i]);

       hmin[,i]:=hmax[,i];

     end;

   for i:= to trunc(ln(n)/ln())+ do

     for j:= to n-( shl i)+ do

       begin

         hmin[i,j]:=min(hmin[i-,j],hmin[i-,j+( shl (i-))]);

         hmax[i,j]:=max(hmax[i-,j],hmax[i-,j+( shl (i-))]);

       end;

   for i:= to q do

     begin

       readln(f,t);

       times:=trunc(ln(t-f+)/ln());

       writeln(max(hmax[times,f],hmax[times,t-( shl times)+])-

               min(hmin[times,f],hmin[times,t-( shl times)+]));

     end;

 end.