#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
const int _maxn=1000100;
int tree[_maxn<<2],M,n;
void push(int y1,int y2){
	y1+=M;
	tree[y1]=y2;
	y1>>=1;
	while(y1){
		tree[y1]=max(tree[(y1<<1)+1],tree[y1<<1]);
		y1>>=1;
	}
}
void read(){
	int x;
	scanf("%d",&n);
	M=1<<(int)log2(n+2)+1;
	for(int i=1;i<=n+1;i++){
		scanf("%d",&x);
		push(i,x);
	}
}
void solve(){
	int q,y1,y2,ans;
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		ans=-2100000000;
		scanf("%d%d",&y1,&y2);
		y1++;
		y2++;
		y1+=M;
		y2+=M;
		y1--;
		y2++;
		while(y1^y2^1){
			if(~y1&1)	ans=max(ans,tree[y1^1]);
			if(y2&1)	ans=max(ans,tree[y2^1]);
			y1>>=1;
			y2>>=1;
		}
		printf("%d\n",ans);
	}
}
int main(){
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	read();
	solve();
	return 0;
}