#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;

const int MAXN = 2e5 + 10;

struct SegTree
{
    int sum;
    int lson, rson;
    SegTree(int _val) : sum(_val), lson(-1), rson(-1) {};
    SegTree(int _val, int _lson, int _rson) : sum(_val), lson(_lson), rson(_rson) {};
};

vector<SegTree> Tree;
vector<int> num;
unordered_map<int, int> mp1, mp2;  // mp1 : num => idx, mp2 : idx => num
int root[MAXN];

int pushdown(int lson, int rson)
{
    SegTree now(Tree[lson].sum + Tree[rson].sum, lson, rson);
    Tree.push_back(now);
    return Tree.size() - 1;
}

int build_null(int s, int t)
{
    if(s == t)
    {
        Tree.push_back(SegTree(0));
        return Tree.size() - 1;
    }
    int mid = (s + t) / 2;
    int ls = build_null(s, mid);
    int rs = build_null(mid + 1, t);
    Tree.push_back(SegTree(0, ls, rs));
    return Tree.size() - 1;
}

int add(int p, int idx, int s, int t)
{
    if(s == t)
    {
        Tree.push_back(SegTree(Tree[s].sum + 1));
        return Tree.size() - 1;
    }
    int mid = (s + t) / 2;
    int ls = Tree[p].lson, rs = Tree[p].rson;
    if(idx <= mid)
        ls = add(ls, idx, s, mid);
    else
        rs = add(rs, idx, mid + 1, t);
    return pushdown(ls, rs);
}

int query(int p1, int p2, int k, int s, int t)  // p1 => l, p2 => r
{
    if(s == t)
        return s;
    int mid = (s + t) / 2;
    int tmp = Tree[Tree[p2].lson].sum - Tree[Tree[p1].lson].sum;
    if(tmp >= k)
        return query(Tree[p1].lson, Tree[p2].lson, k, s, mid);
    else
        return query(Tree[p1].rson, Tree[p2].rson, k - tmp, mid + 1, t);
}

int main()
{
    int n, m;
    cin >> n >> m;
    num.resize(n);
    for(auto &i : num)
        cin >> i;
    vector<int> tmp = num;
    sort(num.begin(), num.end());
    auto lst = unique(num.begin(), num.end());
    num.erase(lst, num.end());
    for(int i = 1; i <= num.size(); ++i)
        mp1[num[i - 1]] = i, mp2[i] = num[i - 1];
    root[0] = build_null(1, num.size());
    for(int i = 1; i <= n; ++i)
        root[i] = add(root[i - 1], mp1[tmp[i - 1]], 1, num.size());
    /*  // 
    vector<int> tmp = num;
    sort(num.begin(), num.end());
    auto lst = unique(num.begin(), num.end());
    num.erase(lst, num.end());
    for(int i = 0; i < tmp.size(); ++i)
        tmp[i] = lower_bound(num.begin(), num.end(), tmp[i]) - num.begin() + 1;
    root[0] = build_null(1, num.size());
    for(int i = 1; i <= n; ++i)
        root[i] = add(root[i - 1], tmp[i - 1], 1, num.size());
    */
    for(int i = 0; i < m; ++i)
    {
        int l, r, k;
        cin >> l >> r >> k;
        int idx = query(root[l - 1], root[r], k, 1, num.size());
        cout << mp2[idx] << "\n";
        // cout << num[idx - 1] << "\n";
    }
    return 0;
}

讨论区中敲警钟的都以及排查过了；应该不是离散化的问题（注释中的代码是另一种离散化方式的代码，二者输出完全相同）