//区间最值问题

//状态表示：从i开始，长度是2^j区间的最大值
//状态计算：f(i,j)=max(f(i,j-1),f(i+2^j-1,j-1))

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;

const int N=200010,M=18;
int n,m;
int w[N];
int f[N][M];

void init()
{
    for(int j=0;j<M;j++)
        for(int i=1;i+(1<<j)<=n;i++)
            if(!j)f[i][j]=w[i];//如果j等0，就处理了单个元素的区间
            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()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];

    init();
    cin>>m;
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        cout<<query(l,r)<<endl;
    }
    return 0;
}