SparceTable

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int inf = 1e9 + 7;

struct Node {
    int mx = -inf, id = -1;
};

struct Sparce {
    vector<int> lg;
    vector<vector<Node>> sp;
    int k, n;
    void build(int _n, int _k, vector<int>& a) {
        k = _k;
        n = _n;
        lg.resize(1 << k, 0);
        sp.resize(k, vector<Node>(n));
        for (int i = 0; i < n; i++) {
            sp[0][i] = { a[i], i };
        }
        for (int i = 2; i < lg.size(); i++) {
            lg[i] = lg[i / 2] + 1;
        }
        for (int j = 1; j < k; j++) {
            for (int i = 0; i + (1 << (j - 1)) < n; i++) {
                unite(sp[j - 1][i], sp[j - 1][i + (1 << (j - 1))], sp[j][i]);
            }
        }
    }

    void unite(const Node& l, const Node& r, Node& m) {
        if (l.mx > r.mx) {
            m = l;
        }
        else {
            m = r;
        }
    }

    void get(int l, int r, Node& res) {
        int lgs = lg[r - l + 1];
        unite(sp[lgs][l], sp[lgs][max(0, r - (1 << lgs) + 1)], res);
        return;
    }
};

int main() {
    int n, i, k, l, r;
    cin >> n;
    Node res;
    vector <int> a(n);
    for (i = 0; i < n; i++) {
        cin >> a[i];
    }
    Sparce Q;
    Q.build(n, (int)ceil(log2(n)) + 1, a);
    cin >> k;
    for (i = 0; i < k; i++) {
        cin >> l >> r;
        Q.get(l - 1, r - 1, res);
        cout << res.mx << " " << res.id + 1 << "\n";
    }
}