#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;
int n,m,a[1000100],d[1000100][50];
int read()
{
    int x=0,f=1;  char ch=getchar();
    while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
    while(ch>='0'&&ch<='9')  {x=(x<<3)+(x<<1)+ch-'0';  ch=getchar();}
    return x*f;
}
void ST_prepare()
{
	for(int i=0;i<=n;i++)  d[i][0]=a[i];
	for(int j=1;(1<<j)<=n;j++)
		for(int i=0;i+(1<<j)-1<=n;i++)
			d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}
int ST_RMQ(int L,int R)
{
	int k=0;
	while((1<<(k+1))<=R-L+1)  k++;
	return max(d[L][k],d[R-(1<<k)+1][k]);
}
void ST_ask()
{
	m=read();
	while(m--)
	{
		int L,R;
		L=read();  R=read();
		cout<<ST_RMQ(L,R)<<endl;
	}
	return;
}
int main()
{
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	n=read();
	for(int i=0;i<=n;i++)
		a[i]=read();
	ST_prepare();
	ST_ask();
	return 0;
}