#include <bits/stdc++.h>

using namespace std;

int getmax(int tree[], int id, int id_left, int id_right, int ans_left, int ans_right){
    if(id_right <= ans_left || ans_right <= id_left)
        return 0;
    if(ans_left <= id_left &&  id_right <= ans_right)
        return tree[id];
    int m = (id_left + id_right) / 2;
    return max(getmax(tree, 2 * id, id_left, m, ans_left, ans_right), getmax(tree, 2 * id + 1, m, id_right, ans_left, ans_right));
}

void build (int tree[], int a[], int v, int tl, int tr) {
    if (tl == tr)
        tree[v] = a[tl];
    else {
        int tm = (tl + tr) / 2;
        build (tree, a, v*2, tl, tm);
        build (tree, a, v*2+1, tm + 1, tr);
        tree[v] = max(tree[v*2], tree[v*2+1]);
    }
}

void update(int tree[], int id, int id_left, int id_right, int val, int ans_id){
    if(ans_id == id_left && id_right == id_left + 1){
        tree[id] = val;
        return;
    }
    int m = (id_left + id_right) / 2;
    if(ans_id >= m)
        update(tree, 2 * id, m, id_right, ans_id, val);
    else
        update(tree, 2 * id, id_left, m, ans_id, val);
    tree[id] = max(tree[id * 2], tree[id * 2 + 1]);

}

void push(int tree[], int excess[], int id, int id_left, int id_right){
    tree[id] += (id_right - id_left) * excess[id];
    if (id_right > id_left + 1){
        excess[2 * id] += excess[id];
        excess[2 * id + 1] += excess[id];
    }
    excess[id] = 0;
}

int main()
{
    int n;
    cin >> n;
    int tree[4*n];
    int a[n];
    for(int i = 0; i < n; ++i){
        int t;
        cin >> t;
        a[i] = t;
    }
    build(tree, a, 1, 0, n - 1);
    int k;
    cin >> k;
    for(int i = 0; i < k; ++i){
        int l, r;
        cin >> l >> r;
        cout << getmax(tree, 1, 0, n - 1, l - 1, r - 1) << endl;
    }
    return 0;
}