为什么第一次输出的是对的，后面输出的都跟第一次一样

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iterator>
#include <map>
#include <unordered_map>
#include <queue>
#include <string>
#include <cstring>
#include <set>
#include <bitset>
#include <unordered_set>
#include <vector>
#include <deque>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <list>
#include <array>
#include <iterator>
#include <cmath>
#include <new>
#include <random>
#include <cfloat>
#include <cstdlib>
#include <climits>
#include <numeric>
#include <complex>
#include <ctime>
#include <chrono>
#include <thread>
#include <mutex>
#include <future>
#include <exception>
#include <stdexcept>
#include <cstdint>
#include <cassert>
#include <stack>
#include <cctype>
#define Ofile(s) freopen(s".in", "r", stdin), freopen (s".out", "w", stdout)
#define Cfile(s) fclose(stdin), fclose(stdout)
#define mod 998244353
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define maxn 100005
using namespace std;

int n, m, cnt, tot;
int rt[maxn << 2], lsh[maxn << 2], node[maxn << 2];

struct edge {
	int v, ls, rs;
} t[maxn << 8];

int query(int o1, int o2, int l, int r, int q) {
	if (l == r)
		return 1;
	int mid = (l + r) / 2, tmp = t[t[o2].ls].v - t[t[o1].ls].v;
	if (tmp >= q)
		return query(t[o1].ls, t[o2].ls, l, mid, q);
	else
		return query(t[o1].rs, t[o2].rs, mid + 1, r, q - tmp);
}

void pushup(int o) {
	t[o].v = t[t[o].ls].v + t[t[o].rs].v;
}

void change(int lsto, int &o, int l, int r, int q, int v) {
	if (!o)
		o = ++cnt;
	if (l == r) {
		t[o].v += v;
		return;
	}
	int mid = (l + r) / 2;
	if (q <= mid) {
		t[o].rs = t[lsto].rs;
		t[o].ls = ++cnt;
		t[t[o].ls] = t[t[lsto].ls];
		change(t[lsto].ls, t[o].ls, l, mid, q, v);
	} else {
		t[o].ls = t[lsto].ls;
		t[o].rs = ++cnt;
		t[t[o].rs] = t[t[lsto].rs];
		change(t[lsto].rs, t[o].rs, mid + 1, r, q, v);
	}
	pushup(o);
}

int main() {
#ifndef ONLINE_JUDGE
	//Ofile("");
	//Cfile("");
#endif
	fast;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> node[i], lsh[i] = node[i];
	sort (lsh + 1, lsh + n + 1);
	tot = unique(lsh + 1, lsh + n + 1) - (lsh + 1);
	for (int i = 1; i <= n; i++) {
		node[i] = lower_bound(lsh + 1, lsh + tot + 1, node[i]) - lsh;
		change(rt[i - 1], rt[i], 1, tot, node[i], 1);
	}
	while (m--) {
		int l, r, q;
		cin >> l >> r >> q;
		cout << lsh[query(rt[l - 1], rt[r], 1, tot, q)] << endl;
	}
	return 0;
}