记录

#include <bits/stdc++.h>
#define int long long
namespace ZBOI {
    inline int read() {
        int f = 0, n = 1;
        char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') n *= -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            f = (f << 1) + (f << 3) + (ch ^ 48);
            ch = getchar(); 
        }
        return f * n;
    }
}
using namespace std;
using namespace ZBOI;
struct Tree {
    int siz, l, r;
} t[200005 << 5];
struct Number {
    int val, id, w;
} a[200005];
bool cmpA(Number x, Number y) {
    if (x.val == y.val) return x.id < y.id;
    return x.val < y.val;
}
bool cmpB(Number x, Number y) {
    return x.id < y.id;
}
int n, m, Len, h[200005];
int root[200005], tot, W;
void build(int p, int l, int r) {
    if (l == r) { return; }
    int mid = l + r >> 1;
    t[p].l = ++ tot, t[p].r = ++ tot;
    build(t[p].l, 1, mid), build(t[p].r, mid + 1, r);
}
int insert(int p, int l, int r, int val) {
    if (l == r && l == val) {
        t[++ tot].siz = t[p].siz + 1;
        t[tot].l = t[p].l, t[tot].r = t[p].r;
        return tot;
    }
    int mid = l + r >> 1, pid = 0, flag = 0;
    if (val <= mid) pid = insert(t[p].l, l, mid, val), flag = -1;
    else pid = insert(t[p].r, mid + 1, r, val), flag = 1;
    t[++ tot].siz = t[p].siz + 1;
    if (flag < 0) t[tot].l = pid, t[tot].r = t[p].r;
    else t[tot].l = t[p].l, t[tot].r = pid;
    return tot;
}
int query(int u, int v, int l, int r, int k) {
    if (l >= r) return l;
    int delsiz = t[t[v].l].siz - t[t[u].l].siz;
    int mid = l + r >> 1;
    if (delsiz >= k) return query(t[u].l, t[v].l, l, mid, k);
    else return query(t[u].r, t[v].r, mid + 1, r, k - delsiz);
}
signed main() {
    n = read(), m = read();
    for (int i = 1; i <= n; ++ i) { a[i].val = read(), a[i].id = i; }
    sort(a + 1, a + n + 1, cmpA);
    for (int i = 1; i <= n; ++ i) {
        if (a[i].val != a[i - 1].val) ++ Len;
        a[i].w = Len;
        h[Len] = a[i].val;
    }
    sort(a + 1, a + n + 1, cmpB);
    root[0] = ++ tot;
    build(root[0], 1, Len);
    for (int i = 1; i <= n; ++ i) root[i] = insert(root[i - 1], 1, Len, a[i].w);
    for (int i = 1; i <= m; ++ i) {
        int l = read(), r = read(), k = read();
        int w = query(root[l - 1], root[r], 1, Len, k);
        cout << h[w] << '\n';
        // cout << w << '\n';
    }
    return 0;
}