#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int MAXN=1000010;
int trees[MAXN<<2];
inline int max(const int a,const int b){
	return a>b ? a:b ;
}

int build_tree(int dir,int l,int r){
    if(l==r) {scanf("%d",&trees[dir]);return trees[dir];}
    int mid=(l+r)>>1;
    int tl=build_tree(dir<<1,l,mid);
    int tr=build_tree(dir<<1|1,mid+1,r);
    return trees[dir]=max(tl,tr);
}

int tree_find(int dir,int l,int r,int tl,int tr){
    if( tl<=l && tr>=r) return trees[dir];
    int mid=(l+r)>>1;
    if(tr<=mid) return tree_find(dir<<1,l,mid,tl,tr);
    else if(tl>mid) return tree_find(dir<<1|1,mid+1,r,tl,tr);
    else{     
		int t1=tree_find(dir<<1,l,mid,tl,tr);         
		int t2=tree_find(dir<<1|1,mid+1,r,tl,tr);
	    return max(t1,t2);
    }
}

int main(){
        freopen("climb.in","r",stdin);
        freopen("climb.out","w",stdout);
        memset(trees,-1,sizeof(trees));
        int n;scanf("%d",&n);
        build_tree(1,0,n);
        int Q;scanf("%d",&Q);
        for(int i=0;i<Q;i++){
                int tl,tr;scanf("%d%d",&tl,&tr);
                int t=tree_find(1,0,n,tl,tr);
                printf("%d\n",t);
        }
        return 0;
}