var n,m,i,j,k,x,y:longint;
    a,b:array[1..100000] of longint;
    
procedure bmin;
var i,j,r:longint;
begin
  j:=0;
  i:=0;
  while i<n do begin
    inc(j);
    inc(i);
    r:=i;
    b[j]:=i;
    for i:=r to r+k-1 do begin
      if a[j]>a[i] then b[j]:=i;
      if i=n then break;
    end;
  end;
  for i:=1 to j do write(a[b[i]],' ');
  writeln;
end;

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

procedure rmq(x,y:longint);
var i,j,m,x1,y1,m1,m2:longint;
begin
  x1:=x div k+1;
  y1:=y div k;
  m:=a[b[x1]];
  writeln(x1,' ',y1);
  for i:=x1+1 to y1 do begin
    if m>a[b[i]] then m:=a[b[i]];
  end;
//  if b[x1]>=x then m1:=a[b[x1]]
//  else begin
    m1:=a[x];
    for i:=x+1 to (x1-1)*k do 
      if m1>a[i] then m1:=a[i];
//  end;
//  if b[y1+1]<=y then m2:=a[b[y1+1]]
//  else begin
    m2:=a[y];
    for i:=y-1 downto y1*k+1 do 
      if m2>a[i] then m2:=a[i];
//  end;
  writeln(m1,' ',m,' ',m2);
  writeln(min(m,m1,m2));
end;
    
begin
  assign(input,'rmq.in');
  assign(output,'rmq.out');
  reset(input);
  rewrite(output);
  read(n,m);
  k:=trunc(sqrt(n));
  for i:=1 to n do read(a[i]);
  bmin;
  for i:=1 to m do begin
    read(x,y);
    rmq(x,y);
  end;
end.