#include<bits/stdc++.h>
#define ULL unsigned long long
#define int long long
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define all(v) v.begin(), v.end()
#define PII pair<int,int>
using namespace std;
constexpr int N =  2 *1e5 + 10,M = 5 * 1e4 + 10,inf = 0x3f3f3f3f;

const int MAXN = 21;

int n,q;
int w[N];
int maxf[N][MAXN];
void init()
{
    for(int j=0;j<MAXN;j++)
    {
        for(int i=1;i + (1 << j) - 1 <= n ; i++)
        {
            if(!j) maxf[i][j] = w[i];
            else
            {
                maxf[i][j] = max(maxf[i][j-1],maxf[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(maxf[l][k],maxf[r - (1<<k) + 1][k]);
}
void solve()
{
    cin >> n;
    for(int i=1;i<=n;i++) cin >> w[i];
    init();
    cin >> q;
    while (q--)
    {
        int l,r;
        cin>>l>>r;
        cout<<query(l,r)<<endl;
    }
    
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
    // cin>>_;
    while(_--)
    {
        solve();
    }
    return 0;
}

/**
 *    author: Nijika_jia
 *    created: 2024.10.22 22:43:14
 */