A

#include <algorithm>
#include <iostream>
#include <array>
#include <vector>
#include <numeric>
#include <random>
#include <chrono>
#include <set>
#include <map>
#include <queue>

#define int long long
using namespace std;

const long long INF = 1e9 + 7;
const int MAXN = 1e5 + 1000;
const int N = 1e5 + 10;

array<int, MAXN> sq, a;
const int B = 666;

inline void build(int n) {
    sq.fill(-INF);
    for (int i = 0; i < n; ++i) {
        sq[i / B] = max(sq[i / B], a[i]);
    }
}

inline int get(int l, int r) {
    int ans = -INF;
    while (l <= r) {
        if (l % B == 0 && l + B - 1 <= r) {
            ans = max(ans, sq[l / B]);
            l += B;
        } else {
            ans = max(ans, a[l]);
            ++l;
        }
    }
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    build(n);
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        cout << get(l, r) << ' ';
    }
}