#include<bits/stdc++.h>

using namespace std;

#define int long long 

int a[500000]={0},tree[550000]={0};

int build(int i,int l,int r){

	if(l+1==r)tree[i]=a[l];

	else{

		int m=(l+r)/2;

		tree[i]=max(build(i*2+1,l,m),build(i*2+2,m,r));

	}

	return tree[i];

}

int search(int s,int e,int l,int r,int i){//s e中找l r 

	if(l==s&&e==r)return tree[i];//s=l  r=e

	int m=(s+e)/2,ls=i*2+1,rs=i*2+2;

	if(l>=m)return search(m,e,l,r,rs);//s m l  r e

	if(r<=m)return search(s,m,l,r,ls);//s l  r m e

	return max(search(s,m,l,m,ls),search(m,e,m,r,rs));//s l m r e

}

signed main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int n;cin>>n;

	for(int i=0;i<n;i++)cin>>a[i];

	build(0,0,n);

	int q;cin>>q;

	while(q--){

		int l,r;cin>>l>>r;

		if(r<l)swap(r,l);

		cout<<search(0,n,l-1,r,0)<<"\n";

	}

	return 0;

}