#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1000010;
int dp[N][20],n,m,t[20];
int main()
{
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	for (int i=0;i<20;i++) t[i]=(1<<i);
	scanf("%d",&n);n++;
	for (int i=1;i<=n;i++) scanf("%d",&dp[i][0]);
	for (int j=1;j<20;j++)
	for (int i=1;i<=n-t[j]+1;i++)
		dp[i][j]=max(dp[i][j-1],dp[i+t[j-1]][j-1]);
	scanf("%d",&m);
	while (m--){
		int l,r;
		scanf("%d%d",&l,&r);
		l++;r++;
		int lg=log2(r-l+1);
		printf("%d\n",max(dp[l][lg],dp[r-t[lg]+1][lg]));
	}
	return 0;
}