#include <algorithm>#include <cstdio>#include <iostream>#include <vector>#include <cstring>#include <queue>#include <cmath>#include <set>#include <map>#define lson l,mid,u << 1#define rson mid + 1,r,u << 1 | 1#define ls u << 1#define rs u << 1 | 1#define mid ((l + r) >> 1)using namespace std;typedef long long ll;const int MAXN = 1e5 + 10;struct segTree{ int tree[21][MAXN],toleft[21][MAXN],sa[MAXN]; void unit(int n) { for(int i = 1; i <= n; i++) {scanf("%d",&tree[1][i]);sa[i] = tree[1][i]; } sort(sa+1,sa+1+n); } void build(int l,int r,int u,int deep) { if(l == r) return; int tmp = mid - l + 1,posl,posr; for(int i = l; i <= r; i++) if(tree[deep][i] < sa[mid]) tmp--; posl = l,posr = mid + 1; for(int i = l; i <= r; i++) { if(i == l) toleft[deep][i] = 0; else toleft[deep][i] = toleft[deep][i - 1]; if(tree[deep][i] < sa[mid]) toleft[deep][i]++,tree[deep + 1][posl++] = tree[deep][i]; else if(tree[deep][i] > sa[mid]) tree[deep + 1][posr++] = tree[deep][i]; else { if(tmp) { toleft[deep][i]++; tree[deep + 1][posl++] = tree[deep][i]; tmp--; } else tree[deep + 1][posr++] = tree[deep][i]; } } build(lson,deep+1); build(rson,deep+1); } int find_k(int l,int r,int u,int L,int R,int k,int deep) { if(L == R) return tree[deep][L]; int s1,s2,newl,newr; if(l == L) s1 = 0; else s1 = toleft[deep][L - 1]; s2 = toleft[deep][R] - s1; if(s2 >= k) { newl = l + s1; newr = newl + s2 - 1; return find_k(lson,newl,newr,k,deep+1); } else { newl = mid + L - l - s1 + 1; newr = R - L - s2 + newl; return find_k(rson,newl,newr,k - s2,deep+1); } }}ac;int main(){ int n,m,l,r,k; scanf("%d %d",&n,&m); ac.unit(n); ac.build(1,n,1,1); while(m--) { scanf("%d %d %d",&l,&r,&k); printf("%dn",ac.find_k(1,n,1,l,r,k,1)); } return 0;}
