#include <cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn = 1e6+100;
const int INF = 10000;
int n, q, H[maxn];
int maxv[2*maxn], qL, qR;
int max(int a, int b) 
{ return a<b?b:a; }
void build(int o, int L, int R) {
	if(L == R) {
		maxv[o] = H[L];
		return;
	} else {
		int M = L + (R-L)/2;
		build(o*2, L, M);
		build(o*2+1, M+1, R);
		maxv[o] = max(maxv[o*2], maxv[o*2+1]);
	}
}
int query(int o, int L, int R) {

	if(R < qL || L > qR) return 0;
	int ans = 0, M = L + (R-L)/2;
	if(L >= qL && R <= qR) return maxv[o];
	if(M >= qL) ans = max(ans, query(o*2, L, M));
	if(M < qR) ans = max(ans, query(o*2+1, M+1, R));
	return ans;
}
int main() {
	freopen("climb.in", "r",stdin);
	freopen("climb.out", "w",stdout);
	scanf( "%d", &n);
	for(int i = 1; i <= n+1; i++) scanf( "%d", &H[i]);
	build(1, 1, n+1);
	scanf( "%d", &q);
	for(int i = 1; i <= q; i++) 
	{
		scanf("%d%d", &qL, &qR);
		qL++; qR++;
		printf("%d\n", query(1, 1, n+1));
	}
	return 0;
}