var
  n,q,i,l,k,x,y:longint;
  a:array [1..50000] of longint;
  b:array [1..1000] of record
      big,small:longint;
    end;
function min(a,b,c:longint):longint;
  var
    t:longint;
  begin
    if a<b then t:=a else t:=b;
    if c<t then t:=c; exit(t);
  end;
function max(a,b,c:longint):longint;
  var
    t:longint;
  begin
    if a>b then t:=a else t:=b;
    if c>t then t:=c; exit(t);
  end;
function findsmall(x,y:longint):longint;
  var
    i:longint;
  begin
    if y<x then exit(maxlongint); findsmall:=maxlongint;
    for i:=x to y do if a[i]<findsmall then findsmall:=a[i];
  end;
function findbig(x,y:longint):longint;
  var
    i:longint;
  begin
    if y<x then exit(0); findbig:=0;
    for i:=x to y do if a[i]>findbig then findbig:=a[i];
  end;
function rmqsmall(x,y:longint):longint;
  var
    i:longint;
  begin
    if y<x then exit(maxlongint); rmqsmall:=maxlongint;
    for i:=x to y do if b[i].small<rmqsmall then rmqsmall:=b[i].small;
  end;
function rmqbig(x,y:longint):longint;
  var
    i:longint;
  begin
    if y<x then exit(0); rmqbig:=0;
    for i:=x to y do if b[i].big>rmqbig then rmqbig:=b[i].big;
  end;
function smallest(x,y:longint):longint;
  begin
    if x=y then exit(a[x]);
    exit(min(findsmall(x,(x div l)+l),rmqsmall(x div l+1,y div l),findsmall((y div l)*l,y)));
  end;
function biggest(x,y:longint):longint;
  begin
    if x=y then exit(a[x]);
    exit(max(findbig(x,(x div l)+l),rmqbig(x div l+1,y div l),findbig((y div l)*l,y)));
  end;
begin
  while not eof do
    begin
      readln (n,q);
      l:=trunc(sqrt(n));
      for i:=1 to 1000 do begin b[i].small:=maxlongint; b[i].big:=0; end;
      k:=1;
      for i:=1 to n do
        begin
          readln (a[i]);
          if (i mod l=0) then inc (k);
          if a[i]>b[k].big then b[k].big:=a[i];
          if a[i]<b[k].small then b[k].small:=a[i];
        end;
      for i:=1 to q do
        begin
          readln (x,y);
          if x>y then begin k:=y; y:=x; x:=k end;
          writeln (biggest(x,y)-smallest(x,y));
        end;
    end;
end.