#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>

using namespace std;

int rmq_matrix[100000][17];
int nr_numbers;

void
build_rmq(void)
{
    int max_upper(floor(log(nr_numbers) / log(2)) + 1);

    for (int i = 1; i != max_upper; ++i) {
        for (int j = 0; j != nr_numbers - (1 << (i - 1)); ++j) {
            rmq_matrix[j][i] = max(rmq_matrix[j][i - 1], rmq_matrix[j + (1 << (i - 1))][i - 1]);
        }
    }

    return;
}

void
scan_data(void)
{
    int n;

    scanf("%d", &n);
    nr_numbers = n;
    for (int i = 0; i != n; ++i) {
        int t;

        scanf("%d", &t);
        rmq_matrix[i][0] = t;
    }

    build_rmq();

    return;
}

int
rmq(int a, int b)
{
    if (a == b) {
        return rmq_matrix[a][0];
    } else {
        int t(floor(log(b - a + 1) / log(2)));

        return max(rmq_matrix[a][t], rmq_matrix[b - (1 << t) + 1][t]);
    }
}

int
main()
{
    int n;

    freopen("test.txt", "r", stdin);
    scan_data();
    scanf("%d", &n);
    while (n--) {
        int a, b;
        int k;

        scanf("%d%d", &a, &b);
        --a; --b;
        printf("%d\n", rmq(a, b));
    }

    return 0;
}