#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 1000005
using namespace std;
int n, m, x, y, a;
struct nond {
	int ll, rr;
	int high;
}tree[4*N];
void up(int now) {
	tree[now].high = max(tree[now*2].high, tree[now*2+1].high);
}
void build(int now, int l, int r) {
	tree[now].ll = l; tree[now].rr = r;
	if(l == r) {
		scanf("%d", &tree[now].high);
		return ;
	}
	int mid = (l+r) >> 1;
	build(now*2, l, mid);
	build(now*2+1, mid+1, r);
	up(now);
}
int query(int now, int l, int r) {
	if(tree[now].ll==l && tree[now].rr==r) return tree[now].high;
	int mid = (tree[now].ll+tree[now].rr) >> 1;
	if(l<=mid && mid<r) return max(query(now*2, l, mid), query(now*2+1, mid+1, r));
	else if(r<=mid) return query(now*2, l, r);
	else return query(now*2+1, l, r);
}
int main() {
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	scanf("%d", &n);
	build(1, 1, n+1);
	scanf("%d", &m);
	for(int i = 1; i <= m; i++) {
		scanf("%d%d", &x, &y);
		printf("%d\n", query(1, x+1, y+1));
	}
	fclose(stdin); fclose(stdout);
	return 0;
}