var v:array[-1..100000,-1..40]of longint;
    a,l:array[1..100000]of longint;
    n,i,j,k,m,u,x,y,o:longint;
    f,q:text;
function min(a,b:longint):longint;
begin
   if a<b then min:=a
          else min:=b;
end;
begin
   assign(f,'rmq.in');
   assign(q,'rmq.out');
   rewrite(q);
   reset(f);
   read(f,n,m);
   for i:=1 to n do
      read(f,a[i]);
   for i:=1 to n do
      v[i,0]:=a[i];
   while 1 shl(u+1)<=n do
      u:=u+1;
   for i:=1 to m do
     if 1 shl (l[i-1]+1)<i then l[i]:=l[i-1]+1
                           else l[i]:=l[i-1];
   for j:=1 to u do
      for i:=1 to n-(1 shl j)+1 do
         v[i,j]:=min(v[i,j-1],v[i+(1 shl(j-1)),j-1]);
   for i:=1 to m do
     begin
       read(f,x,y);
       o:=l[y-x+1];
       writeln(y,min(v[x,o],v[y-(1 shl o),o]));
     end;
   close(f);
   close(q);
end.