求区间内出现次数严格大于 $\frac{r-l+1}{k}$ 的最小数。

显然莫队就好了，但是比较危，可能被卡。

做法 1

考虑设 $gap = \frac{r-l+1}{k}$。则从小到大排序区间后，每隔 $gap$ 个选一个数，答案一定在选出的数集之中。
因此考虑把这些数取出来，并判断它的出现次数是否达到要求即可。由于 $k$ 特别小，所以取出的数也特别少，可以接受。

做法 2

在主席树上优先跳左区间，不行再跳右区间。
由于在跳左区间之前特判了左区间的数字数量，所以最多只会跳错 $k$ 次，也可以接受。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 15;
int n, q, a[N], rt[N], tot = 0;
struct Tree { int ls, rs, sum; } tr[N << 6];
void change(int &u, int l, int r, int x) {
    tr[++tot] = tr[u], u = tot, tr[u].sum++;
    if (l == r) return;
    int mid = l + r >> 1;
    if (x <= mid) change(tr[u].ls, l, mid, x);
    else change(tr[u].rs, mid + 1, r, x);
}
int query(int u, int v, int l, int r, int k) {
    if (l == r) return (tr[u].sum - tr[v].sum >= k) ? l : -1;
    int mid = l + r >> 1, res = -1;
    if (tr[ tr[u].ls ].sum - tr[ tr[v].ls ].sum >= k) res = query(tr[u].ls, tr[v].ls, l, mid, k);
    return (res == -1) ? query(tr[u].rs, tr[v].rs, mid + 1, r, k) : res;
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), rt[i] = rt[i - 1], change(rt[i], 1, n, a[i]);
    while (q--) {
        int l, r, k; scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", query(rt[r], rt[l - 1], 1, n, (r - l + 1) / k + 1) );
    }
    return 0;
}