rmq.segment_tree

const
    inf = maxlongint;
var
    a,t:array[1..100000] of longint;
    i,j,n,m,l,r:longint;

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

procedure build;
var i:longint;
 begin
   for i:=n+1 to n shl 1 do
      t[i]:=a[i-n];
   for i:=n downto 1 do
     t[i]:=max(t[i shl 1],t[(i shl 1) + 1]);
 end;

function rmq(l,r:longint):longint;
var res:longint;
  begin
    inc(l,n);
    inc(r,n);
    res:=-inf;
    while (l<=r) do
      begin
        if (l and 1 = 1) then
           res:=max(res,t[l]);
        if (r and 1 = 0) then
           res:=max(res,t[r]);
        l:=(l+1) shr 1;
        r:=(r-1) shr 1;
    end;
   rmq:=res;
 end;

Begin
  read(n);
  for i:=1 to n do
    read(a[i]);
  build;
  read(m);
  for i:=1 to m do
    begin
     read(l,r);
     writeln(rmq(l,r));
    end;
end.