#include <bits/stdc++.h>
using namespace std;

#define int long long

int n;
vector<int> a;
vector<vector<int> > st;
vector<int> lg(1e6 + 1);

void build() {
    lg[1] = 0;
    for (int i = 2; i <= 1e6; ++i) lg[i] = lg[i/2] + 1;
    for (int i = 0; i<n; ++i) st[0][i] = a[i];
    for (int i = 1; i<20; ++i) {
        for (int j = 0; j + (1 << i) <= n; ++j)
            st[i][j] = max(st[i - 1][j], st[i - 1][j + (1<<(i-1))]);
    }
}

int get_max(int l, int r) {
    int i = lg[r - l + 1];
    return max(st[i][l], st[i][r - (1<<i) + 1]);
}

signed main() {

    cin >> n;
    a.resize(n);
    st.resize(20, vector<int> (n));
    for (int i = 0; i<n; ++i) cin >> a[i];
    build();

    int k;
    cin >> k;
    for (int i = 0; i<k; ++i) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        cout << get_max(l, r) << "\n";
    }

    return 0;
}