uses math;
var a:array[0..200000,0..100] of longint;
k,rmq,q,l,r,n,i,j:longint;
function max(a,b:int64):int64;
begin
if a>b then exit(a)
else exit(b);
end;
begin
readln(n);
for i:=1 to n do read(a[i,0]);
readln;
for j:=1 to trunc(ln(n)/ln(2)) do
for i:=1 to (n-1) shl j+1 do
a[i,j]:=max(a[i,j-1],a[i+1 shl (j-1),j-1]);

readln(q);
for i:=1 to q do
begin
readln(l,r);
k:=trunc(ln(r-l+1)/ln(2));
rmq:=max(a[l,k],a[r-1 shl k+1,k]);
writeln(rmq);
end;
end.