#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int INF = 1e9;

void build (long long* segment_three, const long long a[], int v, int l, int r) {
    if (l == r) {
        segment_three[v] = a[l];
    } else {
        int m = (l + r) / 2;
        build (segment_three, a, v * 2, l, m);
        build (segment_three, a, v * 2 + 1, m + 1, r);
        segment_three[v] = max(segment_three[v * 2], segment_three[v * 2 + 1]);
    }
}

long long get_max(long long segment_three[], int v, int tl, int tr, int l, int r) {
    if (l > r) {
        return -INF;
    }
    if (l == tl && r == tr) {
        return segment_three[v];
    }
    int mid = (tl + tr) / 2;
    return max(get_max(segment_three, v * 2, tl, mid, l, min(mid, r)),
               get_max(segment_three, v * 2 + 1, mid + 1, tr, max(l, mid + 1), r));
}

void update(long long *segment_three, int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        segment_three[v] = new_val;
    } else {
        int mid = (tl + tr) / 2;
        if (pos <= mid) {
            update(segment_three, v * 2, tl, mid, pos, new_val);
        } else {
            update(segment_three, v * 2 + 1, mid + 1, tr, pos, new_val);
        }
        segment_three[v] = max(segment_three[v * 2], segment_three[v * 2 + 1]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n;
    long long data[n];
    long long segment_three[4 * n];
    for (int i = 0; i < 4 * n; ++i)
        segment_three[i] = -INF;
    for (int i = 0; i < n; ++i) {
        cin >> data[i];
    }
    build(segment_three, data, 1, 0, n - 1);
    int l, r, index;
    long long new_val;
    cin >> m;
    char k;
    for (int i = 0; i < m; ++i) {
        cin >> l >> r;
        l--;
        r--;
        if (l > r) {
            swap(l, r);
        }
        cout << get_max(segment_three, 1, 0, n - 1, l, r) << endl;
    }
}