#include <iostream>
#include <cstdio>
#define MAXN 1000000
#define lc i*2
#define rc i*2+1
using namespace std;
struct segtree{
	int l,r,m;
}nd[MAXN<<4];
int n,q,a[MAXN];
inline int read(){
    int k=0;char f=1,c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())k=k*10+c-'0';
    return k*f;
}
void build(int i,int left,int right){
	nd[i].l=left;
	nd[i].r=right;
	if(left==right){
		nd[i].m=a[left];
		return;
	}else{
		int mid=(left+right)/2;
		build(lc,left,mid);
		build(rc,mid+1,right);
	}
	nd[i].m=max(nd[lc].m,nd[rc].m);
	return;
}
int find(int i,int left,int right){
	if(nd[i].l==left&&nd[i].r==right){
		return nd[i].m;
	}else{
		if(left>=nd[lc].l&&right<=nd[lc].r){
			return find(lc,left,right);
		}else if(left>=nd[rc].l&&right<=nd[i].r){
			return find(rc,left,right);
		}else{
			return max(find(lc,left,nd[lc].r),find(rc,nd[rc].l,right));
		}
	}
}
int main(){
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	n=read();
	for(int i=0;i<=n;i++){
		a[i]=read();
	}
	build(1,0,n);
	q=read();
	while(q--){
		int left=read(),right=read();
		printf("%d\n",find(1,left,right));
	}
}