#include"iostream"
using namespace std;
const int maxn=1e4+5;
struct Tree
{
    int l,r,Max;
};
Tree tree[maxn<<2];
int a[maxn];
void BuildTree(int id,int L,int R)
{
    tree[id].l=L;
    tree[id].r=R;
    if(L==R)
    {
        tree[id].Max=a[L];
        return;
    }
    int mid=(L+R)/2;
    BuildTree(id<<1,L,mid);
    BuildTree(id<<1|1,mid+1,R);
    tree[id].Max=max(tree[id<<1].Max,tree[id<<1|1].Max);
}
int Query(int id,int L,int R)
{
    if(L<=tree[id].l&&R>=tree[id].r)return tree[id].Max;
    int mid=(tree[id].l+tree[id].r)/2;
    if(R<=mid)return Query(id<<1,L,R);
    else if(L>mid)return Query(id<<1|1,L,R);
    else return max(Query(id<<1,L,mid),Query(id<<1|1,mid+1,R));

}
int main()
{
    int N;
    while(cin>>N)
    {
        for(int i=0;i<N;i++)cin>>a[i];
        BuildTree(1,0,N-1);

        int M;
        cin>>M;
        for(int i=0;i<M;i++)
        {
            int L,R;
            cin>>L>>R;
            cout<<Query(1,L,R)<<"\n";;
        }
    }
}