SegmentTree

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

using namespace std;

const int inf = 1e9 + 7;

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

struct SegTree {
    vector <Node> t;
    int n;
    SegTree(vector <int>& a) {
        n = (int)a.size() * 4;
        t.resize(n);
        build(1, 0, (int)a.size() - 1, a);
    }
    void unite(const Node& l, const Node& r, Node& m) {
        if (l.mx > r.mx) {
            m = l;
        }
        else {
            m = r;
        }
    }
    void build(int v, int l, int r, vector <int>& a) {
        if (l == r) {
            t[v].mx = a[l];
            t[v].id = l;
        }
        else {
            int m = (l + r) / 2;
            build(2 * v, l, m, a);
            build(2 * v + 1, m + 1, r, a);
            unite(t[2 * v], t[2 * v + 1], t[v]);
        }
    }
    Node query(int v, int l, int r, int ql, int qr) {
        if (qr < l || ql > r) {
            return { -inf, -1 };
        }
        else if (ql <= l && qr >= r) {
            return t[v];
        }
        else {
            int m = (l + r) / 2;
            Node L = query(2 * v, l, m, ql, qr), R = query(2 * v + 1, m + 1, r, ql, qr), M;
            unite(L, R, M);
            return M;
        }
    }
    void update(int v, int l, int r, int idx, int x) {
        if (idx < l || idx > r) {
            return;
        }
        else if (idx <= l && idx >= r) {
            t[v].mx = x;
        }
        else {
            int m = (l + r) / 2;
            update(2 * v, l, m, idx, x);
            update(2 * v + 1, m + 1, r, idx, x);
            unite(t[2 * v], t[2 * v + 1], t[v]);
        }
    }
};

int main() {
    int n;
    cin >> n;
    vector <int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    SegTree tree(a);
    Node res;
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int l, r;
        cin >> l >> r;
        res = tree.query(1, 0, n - 1, l - 1, r - 1);
        cout << res.mx << " " << res.id + 1 << '\n';
    }
    return 0;
}