#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<iomanip>
#include<functional>
#define JW fclose(stdin); fclose(stdout);
using namespace std;
const int maxn=1000000+10;
int n,m,Max[maxn][30];
inline int QR(){
	char ch;
	while(ch=getchar(),ch<'0'||ch>'9');
	int x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
	return x;
}
inline int qmg(int s,int t){
	int m=log2((t-s+1)*1.0);
	int k=1<<(m);
	return max(Max[s][m],Max[t-k+1][m]);
}
int main(){
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	n=QR();
	int a,b;
	for(int i=0;i<=n;i++)Max[i][0]=QR();
	int s=ceil(log2(n*1.0));
	for(int j=1;j<=s;j++){
		for(int i=0;i<=n;i++){
			Max[i][j]=Max[i][j-1];
			int k=1<<(j-1);
			if(i+k<=n)Max[i][j]=max(Max[i][j],Max[i+k][j-1]);
		}
	}
	m=QR();
	for(int i=1;i<=m;i++){
		a=QR(),b=QR();
		printf("%d\n",qmg(a,b));
	}
	return 0;
}