#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn=1e6+10;

int st[maxn][24];
int n;

inline int Query(int l,int r){
	int k=1;
	while((1<<(k))<=(r-l+1))k++;
	k--;
	return max(st[l][k],st[r-(1<<k)+1][k]);
}

int main(){
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	scanf("%d",&n);
	n++;
	for(int i=1;i<=n;i++){
		scanf("%d",&st[i][0]);
	}
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;(1<<j)-1+i<=n;i++){
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
	int e;
	scanf("%d",&e);
	for(int i=1;i<=e;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		x++;y++;
		printf("%d\n",Query(x,y));
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}