#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000010
struct node
{
    int left,right,mx;
}tree[MAXN*4];
int a[MAXN];
int read()
{
    int s=0,fh=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
    return s*fh;
}
void Pushup(int k){tree[k].mx=max(tree[k*2].mx,tree[k*2+1].mx);}
void Build(int k,int l,int r)
{
    tree[k].left=l;tree[k].right=r;
    if(l==r){tree[k].mx=a[l];return;}
    int mid=(l+r)/2;
    Build(k*2,l,mid);
    Build(k*2+1,mid+1,r);
    Pushup(k);
}
int Query(int k,int ql,int qr)
{
    if(ql<=tree[k].left&&tree[k].right<=qr)return tree[k].mx;
    int mid=(tree[k].left+tree[k].right)/2;
    if(qr<=mid)return Query(k*2,ql,qr);
    else if(ql>mid)return Query(k*2+1,ql,qr);
    else return max(Query(k*2,ql,mid),Query(k*2+1,mid+1,qr));
}
int main()
{
    freopen("climb.in","r",stdin);
    freopen("climb.out","w",stdout);
    int n,i,m,ql,qr;
    n=read();
    n++;
    for(i=1;i<=n;i++)a[i]=read();
    Build(1,1,n);
    m=read();
    for(i=1;i<=m;i++)
    {
        ql=read()+1;qr=read()+1;
        printf("%d\n",Query(1,ql,qr));
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}