var f:array [0..50005,0..20,1..2] of longint;
    s:array [0..20] of longint;
    x,y,k,ans,len:longint;
    n,m,i,j,maxi:longint;
procedure doit;
var x,i:longint;
begin
  x:=1;i:=0;
  while x<=n do
    begin
      s[i]:=x;
      x:=x*2;
      inc(i);
    end;
  maxi:=i-1;
end;
function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;
function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;
function check(len:longint):longint;
var i:longint;
begin
  for i:=1 to maxi do
    if len<s[i] then break;
  if len<s[i] then exit(i-1) else exit(i);
end;
begin
  readln(n,m);
  for i:=1 to n do
    begin
      readln(x);
      f[i,0,1]:=x;
      f[i,0,2]:=x;
    end;
  doit;
  for j:=1 to maxi do
    for i:=1 to n-s[j-1] do
      begin
        f[i,j,1]:=max(f[i,j-1,1],f[i+s[j-1],j-1,1]);
        f[i,j,2]:=min(f[i,j-1,2],f[i+s[j-1],j-1,2]);
      end;
  for i:=1 to m do
    begin
      readln(x,y);
      len:=y-x+1;
      k:=check(len);
      ans:=max(f[x,k,1],f[y-s[k]+1,k,1])-min(f[x,k,2],f[y-s[k]+1,k,2]);
      writeln(ans);
    end;
end.