#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+10;
int a[N];
int dp[N][30];
int n, m;

void init() {
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int j = 0; j <= 20; j ++) {
        for (int i = 1; i+(1<<j)-1 <= n; i ++) {
            if(!j) dp[i][j] = a[i];
            else dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
        }
    }
}

int main() {
    cin >> n;
    init();
    cin >> m;
    while(m --) {
        int l, r;
        cin >> l >> r;
        int len = log(r-l+1)/log(2);
        cout << max(dp[l][len], dp[r-(1<<len)+1][len]) << endl;
    }
    return 0;
}