#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int w[N],f[N][18];
int n,m;
void init(){
    for(int j=0;j<18;j++)
        for(int i=1;i+(1<<j)-1<=n;i++){
            if(j==0)f[i][j]=w[i];
            else f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
        } 
}
int query(int l,int r){
    int len=r-l+1;
    int k=log(len)/log(2);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    init();
    scanf("%d",&m);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",query(x,y));
    }
    return 0;
}