WA+RE 20

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, tot, a[N], b[N], rt[N], lc[N << 4], rc[N << 4], val[N << 4];

int build(int s, int t)
{
  int c = ++tot;
  if (s == t)
    return c;
  int mid = (s + t) >> 1;
  lc[c] = build(s, mid);
  rc[c] = build(mid + 1, t);
  return c;
}

int update(int p, int s, int t, int x)
{
  int c = ++tot;
  lc[c] = lc[p], rc[c] = rc[p], val[c] = val[p] + 1;
  if (s < t)
  {
    int mid = (s + t) >> 1;
    if (x <= mid)
      lc[c] = update(lc[c], s, mid, x);
    else
      rc[c] = update(rc[c], mid + 1, t, x);
  }
  return c;
}

int query(int u, int v, int s, int t, int k)
{
  if (s == t)
    return b[s];
  int mid = (s + t) >> 1, cnt = val[lc[v]] - val[lc[u]];
  if (cnt >= k)
    return query(lc[u], lc[v], s, mid, k);
  return query(rc[u], rc[v], mid + 1, t, k - cnt);
}

int main()
{
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++)
    scanf("%d", a + i), b[i] = a[i];
  sort(b + 1, b + n + 1);
  int pos = unique(b + 1, b + n + 1) - b - 1;
  rt[0] = build(1, pos);
  for (int i = 1; i <= n; i++)
  {
    a[i] = lower_bound(b + 1, b + pos + 1, a[i]) - b;
    rt[i] = update(rt[i - 1], 1, pos, a[i]);
  }
  while (m--)
  {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    printf("%d\n", query(rt[l - 1], rt[r], 1, n, k));
  }
  return 0;
}