#include<bits/stdc++.h>
using namespace std;
namespace xiaoxiao{
	#define FO(name) freopen(#name".in","r",stdin),freopen(#name".out","w",stdout)
	#define FC fclose(stdin),fclose(stdout)
	#define test(name) freopen(#name".txt","r",stdin)
	#define ifor(a,b,c) for(int a=(b);a<=(c);++a)
	#define dfor(a,b,c) for(int a=(b);a>=(c);--a)
	#define Max(a,b) ((a)>(b)? (a):(b))
	#define Min(a,b) ((a)<(b)? (a):(b))
	typedef long long LL;
	inline LL QR(){
		char ch;
		bool minus=0;
		LL x=0;
		while(ch=getchar(),ch<'-'||ch>'9');
		if(ch=='-') minus=1,ch=getchar();
		while(x=x*10+ch-48,ch=getchar(),ch>='0'&&ch<='9');
		if(minus) return -x;
		return x;
	}
	inline void QW(LL num,char ch){
		if(num<0) num=-num,putchar('-');
		int cnt=0;
		string str;
		while(str[++cnt]=num%10+'0',num/=10);
		while(putchar(str[cnt]),--cnt);
		putchar(ch);
	}
	inline long double FQR(){
		char ch;
		bool minus=0;
		long double num=0;
		int cnt=0;
		while(ch=getchar(),ch<'-'||ch>'9');
		if(ch=='-') minus=1,ch=getchar();
		while(num=num*10+ch-48,ch=getchar(),ch>='0'&&ch<='9');
		if(ch=='.'){
			ch=getchar();
			while(num+=1.0*(ch-48)/pow(10,++cnt),ch=getchar(),ch>='0'&&ch<='9');
		}
		if(minus) return -num;
		return num;
	}
}
using namespace xiaoxiao;
void work();
int main(){
	FO(climb);
	work();
	FC;
	return 0;
}

const int ma=1e6+10;
int n,q;
int h[ma],rmax[ma][20];

void rmqinit();
int rmqmax(int,int);
void work(){
	n=QR();
	ifor(i,1,n+1) h[i]=rmax[i][0]=QR();
	rmqinit();
	q=QR();
	ifor(i,1,q){
		int a=QR(),b=QR();
		QW(rmqmax(a+1,b+1),'\n');
	}
}
void rmqinit(){
	int m=log(1.0*n)/log(2.0);
	ifor(j,1,m){
		ifor(i,1,n){
			rmax[i][j]=rmax[i][j-1];
			int tmp=1<<(j-1);
			if(i+tmp<=n) rmax[i][j]=Max(rmax[i][j],rmax[i+tmp][j-1]);
		}
	}
}
int rmqmax(int s,int t){
	int m=log(1.0*(t-s+1))/log(2.0),k=1<<m;
	return Max(rmax[s][m],rmax[t-k+1][m]);
}