#include<cstdio>
#include<cstring>
#define lch l,mid,rt<<1
#define rch mid+1,r,rt<<1|1
using namespace std;
namespace mine{
	int __c,__x,__a[110],__i,__j;
	bool __neg;
	inline int getint(){
		__x=__neg=0;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		if(__c=='-'){
			__neg=true;
			__c=getchar();
		}
		for(;__c>='0'&&__c<='9';__c=getchar())__x=(__x<<1)+(__x<<3)+(__c^48);
		if(__neg)return -__x;
		return __x;
	}
	inline void putint(int __x){
		__neg=__x<0;
		if(__neg)__x=-__x;
		__i=0;
		do{
			__a[__i++]=__x%10+48;
			__x/=10;
		}while(__x);
		if(__neg)putchar('-');
		for(__j=__i-1;__j>=0;__j--)putchar(__a[__j]);
	}
}
using namespace mine;
const int maxn=1000010;
int a[maxn<<2];
inline int max(int a,int b){
	return a>b?a:b;
}
void build(int,int,int);
int qery(int,int,int,int,int);
int n,m,s,t;
inline int MAIN(){
#define COGS
#ifdef COGS
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
#endif
	n=getint();
	build(1,n+1,1);
	m=getint();
	for(int i=0;i<m;i++){
		s=getint();
		t=getint();
		putint(qery(s+1,t+1,1,n+1,1));
		putchar('\n');
	}
	return 0;
}
inline void build(int l,int r,int rt){
	if(l==r){
		scanf("%d",&a[rt]);
		return;
	}
	int mid=(l+r)/2;
	build(lch);
	build(rch);
	a[rt]=max(a[rt<<1],a[rt<<1|1]);
}
inline int qery(int s,int t,int l,int r,int rt){
	int mid;
	label:
	if(s<=l&&t>=r)return a[rt];
	mid=(l+r)>>1;
	if(t<=mid){
		r=mid;
		rt<<=1;
		goto label;
	}
	if(s>mid){
		l=mid+1;
		rt<<=1;
		rt|=1;
		goto label;
	}
	return max(qery(s,t,lch),qery(s,t,rch));
}
int hzoier=MAIN();
int main(){;}