#include <bits/stdc++.h>

using i64 = long long;

template<class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;

    SegmentTree() : n(0) {}

    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }

    template<class T>
    SegmentTree(std::vector<T> init_) {
        init(init_);
    }

    void init(int n_, Info v_ = Info()) {
        init(std::vector<Info>(n_, v_));
    }

    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        int sz = (1 << (std::__lg(n - 1) + 1));
        info.assign(sz * 2, Info());
        std::function<void(int, int, int)> build = [&](int v, int l, int r) {
            if (l == r) {
                info[v] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(v + v, l, m);
            build(v + v + 1, m + 1, r);
            info[v] = info[v + v] + info[v + v + 1];
        };
        build(1, 0, n - 1);
    }

    Info rangeQuery(int v, int l, int r, int tl, int tr) {
        if (r < tl || l > tr) {
            return Info();
        }
        if (l >= tl && r <= tr) {
            return info[v];
        }
        int m = (l + r) / 2;
        return rangeQuery(v + v, l, m, tl, tr) + rangeQuery(v + v + 1, m + 1, r, tl, tr);
    }

    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n - 1, l, r);
    }

    void modify(int v, int l, int r, int i, const Info &x) {
        if (l == r) {
            info[v] = x;
            return;
        }
        int m = (l + r) / 2;
        if (i <= m) {
            modify(v + v, l, m, i, x);
        } else {
            modify(v + v + 1, m + 1, r, i, x);
        }
        info[v] = info[v + v] + info[v + v + 1];
    }

    void modify(int i, const Info &x) {
        modify(1, 0, n - 1, i, x);
    }

    Info query(int v, int l, int r, int i) {
        if (l == r) {
            return info[v];
        }
        int m = (l + r) / 2;
        if (i <= m) {
            return query(v + v, l, m, i);
        } else {
            return query(v + v + 1, m + 1, r, i);
        }
    }

    Info query(int i) {
        return query(1, 0, n - 1, i);
    }
};

struct Max {
    i64 max;
    std::array<int, 3> a;

    Max() : max(0) {
        a = {-1, -1, -1};
    }

    Max(i64 x, std::array<int, 3> a) : max(x), a(a) {}
};

Max operator+(const Max &a, const Max &b) {
    if (a.max > b.max) {
        return a;
    } else {
        return b;
    }
}

signed main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    std::vector<std::vector<std::pair<int, int>>> qry(n);
    int q;
    std::cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r;
        std::cin >> l >> r;
        l = n - l;
        r = n - r;
        std::swap(l, r);
        qry[r].emplace_back(l, i);
    }
    std::reverse(a.begin(), a.end());
    std::vector<bool> vis(n + 1);
    std::vector<std::vector<int>> pos(n + 1);
    for (int i = 0; i < n; i++) {
        vis[a[i]] = true;
        pos[a[i]].emplace_back(i);
    }
    std::vector<std::vector<int>> div(n + 1);
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            continue;
        }
        for (int j = i * 2; j <= n; j += i) {
            if (!vis[j]) {
                continue;
            }
            div[j].emplace_back(i);
        }
    }
    std::vector<std::array<int, 3>> res(q, {-1, -1, -1});
    std::vector<i64> dp(n, 0);
    SegmentTree<Max> st(n);
    for (int i = 0; i < n; i++) {
        int x = a[i];
        for (int y : div[x]) {
            auto it1 = std::lower_bound(pos[y].begin(), pos[y].end(), i);
            if (it1 == pos[y].begin()) {
                continue;
            }
            it1--;
            int j = *it1;
            for (int z : div[y]) {
                auto it2 = std::lower_bound(pos[z].begin(), pos[z].end(), j);
                if (it2 == pos[z].begin()) {
                    continue;
                }
                it2--;
                int k = *it2;
                i64 val = a[k] + 1LL * n * a[j] + 1LL * n * n * a[i];
                if (val >= dp[k]) {
                    dp[k] = val;
                    st.modify(k, Max(dp[k], {k, j, i}));
                }
            }
        }
        for (auto qq : qry[i]) {
            int l = qq.first, r = i, id = qq.second;
            res[id] = st.rangeQuery(l, r).a;
        }
    }
    for (int i = 0; i < q; i++) {
        if (res[i][0] == -1) {
            std::cout << "-1\n";
        } else {
            std::cout << n - res[i][2] << " " << n - res[i][1] << " " << n - res[i][0] << "\n";
        }
    }
}