var a:array[0..20,1..100000]of longint;
    buf:array[1..1000000]of longint;
    c:array[1..1000000]of longint;
    b:array[0..20]of longint;
    n,m:longint;

procedure putere;
var i:integer;
begin
 b[0]:=1;
 for i:=1 to 20 do
  b[i]:=b[i-1]*2;
end;

function min(a,b:longint):longint;
begin
 if a>b then min:=b else min:=a;
end;

procedure mat;
var i,j:longint;
begin
 for i:=1 to 17 do
  begin
   for j:=1 to n do a[i,j]:=min(a[i-1,j],a[i-1,min(b[i-1]+j,n)]);
  end;
end;

function cal(x,y:longint):longint;
var k,i,p,m:longint;
begin
 k:=y-x+1; p:=x; m:=1000000;
 for i:=20 downto 0 do
  begin
   if k div b[i]=1 then
    begin
     if a[i,p]<m then m:=a[i,p];
     p:=p+b[i];
     k:=k mod b[i];
    end;
  end;
 cal:=m;
end;

procedure body;
var i,x,y,p,l:longint;f,g:text;
begin
 assign(f,'rmq.in');
 reset(f);
 settextbuf(f,buf);
 assign(g,'rmq.out');
 rewrite(g);
 settextbuf(g,buf);
 readln(f,n,m);
 for i:=1 to n do begin readln(f,p);inc(c[p]); end;
 for i:=0 to 100000 do
  if c[i]>0 then inc(l); a[0,l]:=i; end;
 n:=l;
 mat;
 for i:=1 to m do
  begin
   readln(f,x,y);
   writeln(g,cal(x,y));
  end;
 close(g);
 close(f);
end;



begin
 putere;
 body;
end.