rt

#include<bits/stdc++.h>

using namespace std;

inline int read(){
	int w=0,f=1; char ch;
	while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
	while(isdigit(ch)){
		w=(w<<3)+(w<<1)+(ch^48);
		ch=getchar();
	}
	return w*f;
}

int n,q;
int a[100005],t[400005];
inline int ls(int p){
	return p<<1;
}
inline int rs(int p){
	return p<<1|1;
}
void pushup(int p){
	t[p]=max(t[ls(p)],t[rs(p)]);
}
void build(int p,int l,int r){
	if(l==r){
		t[p]=max(t[p],a[l]);
		return;
	}
	int mid=(l+r)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	pushup(p);
}
int query(int p,int l,int r,int tl,int tr){
	int res=-1e9;
	if(tl<=l&&r<=tr)
		return t[p];
	int mid=(l+r)>>1;
	if(tl<=mid)
		res=max(res,query(ls(p),l,mid,tl,tr));
	if(tr>mid)
		res=max(res,query(rs(p),mid+1,r,tl,tr));
	return res;
}

int main(){
	n=read();
	n++;
	for(int i=1;i<=n;i++) a[i]=read();
	build(1,1,n);
	q=read();
	for(int i=1;i<=q;i++){
		int x=read(),y=read();
		printf("%d\n",query(1,1,n,x+1,y+1));
	}
	return 0;
}