Persistent IT - Sign on fence codeforces

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 1e5;
int ver[N + 1];
struct PersistentIT
{
    struct node
    {
        int l, r, best, pre, suf;
        bool full;
        node()
        {
            l = r = 0;
            best = pre = suf = 1;
            full = true;
        }
        node operator + (node other)
        {
            node tmp;
            tmp.best = max({best, other.best, suf + other.pre});
            tmp.full = full && other.full;
            tmp.pre = pre;
            tmp.suf = other.suf;
            if (full)
            {
                tmp.pre += other.pre;
            }
            if (other.full)
            {
                tmp.suf += suf;
            }
            return tmp;
        }
    };
    vector<node> tree;
    PersistentIT()
    {
        node tmp;
        tmp.full = false;
        tmp.best = tmp.pre = tmp.suf = 0;
        tree.resize(1, tmp);
        ver[0] = 0;
    }
    void refine(int cur)
    {
        int l = tree[cur].l, r = tree[cur].r;
        tree[cur] = tree[tree[cur].l] + tree[tree[cur].r];
        tree[cur].l = l;
        tree[cur].r = r;
    }
    int BuildTree(int L, int R)
    {
        int cur = tree.size();
        node tmp;
        tmp.best = tmp.suf = tmp.pre = tmp.full = 0;
        tree.push_back(tmp);
        if (L != R)
        {
            int mid = (L + R)/2;
            tree[cur].l = BuildTree(L, mid);
            tree[cur].r = BuildTree(mid + 1, R);
        }
        return cur;
    }
    int update(int oldID, int TreeL, int TreeR, int pos)
    {
        int cur = tree.size();
        node tmp;
        tree.push_back(tmp);
        if (TreeL == TreeR)
        {
            return cur;
        }
        int mid = (TreeL + TreeR)/2;
        if (pos <= mid)
        {
            tree[cur].r = tree[oldID].r;
            tree[cur].l = update(tree[oldID].l, TreeL, mid, pos);
            refine(cur);
        }
        else
        {
            tree[cur].l = tree[oldID].l;
            tree[cur].r = update(tree[oldID].r, mid + 1, TreeR, pos);
            refine(cur);
        }
        return cur;
    }
    node get(int v, int TreeL, int TreeR, int l, int r)
    {
        //cerr << v << '\n';
        if (l > r)
        {
            node tmp;
            tmp.full = false;
            tmp.best = tmp.pre = tmp.suf = 0;
            return tmp;
        }
        if (TreeL == l && TreeR == r)
        {
            return tree[v];
        }
        int mid = (TreeL + TreeR)/2;
        return get(tree[v].l, TreeL, mid, l, min(r, mid)) + get(tree[v].r, mid + 1, TreeR, max(l, mid + 1), r);
    }
} Tree;
int id[N + 1], a[N + 1], n;
void read()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i];
        id[i] = i;
    }
    sort(id + 1, id + n + 1, [](const int &x, const int &y)
    {
        return a[x] > a[y];
    });
    Tree.BuildTree(1, n);
    for (int i = 1; i <= n; ++ i)
    {
        ver[i] = Tree.update(ver[i - 1], 1, n, id[i]);
        //cerr << ver[i] << ' ';
    }
}
void solve()
{
    int m;
    cin >> m;
    while(m--)
    {
        int l, r, w;
        cin >> l >> r >> w;
        int low = 1, high = n;
        int k;
        while(low <= high)
        {
            int mid = (low + high)/2;
            if (Tree.get(ver[mid], 1, n, l, r).best >= w)
            {
                k = mid;
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
        //cerr << low << '\n';
        cout << a[id[low]] << '\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}