#include<bits/stdc++.h>
using namespace std;
int Log[20];
void log2_2(){
	Log[0]=1;
	for(int i=1;i<=20;i++)Log[i]=Log[i-1]*2;
} 
int log2_3(int a){
	int ans;
	for(int i=0;i<21;i++)if(Log[i]<=a)ans=i;else return ans;
}
int main(){
	int n,m,l,r,st[10000][20];
	cin>>n;for(int i=0;i<n;i++)cin>>st[i][0];cin>>m;
	for(int i=0;i<n;i++){
		for(int j=1;j<21;j++){
			st[i][j]=max(st[i][-1],st[i+Log[j]][j-1]);
		}
	}
	for(int i=0;i<m;i++){
		cin>>l>>r;
		cout<<max(st[r][log2_3(r-l+1)],st[l-log2_3(r-l+1)][log2_3(r-l+1)]); 
	}
	return 0;
}