| 49 | //the code returns k-th number in a range l to r if the range were sorted |
| 50 | int V[N], root[N], a[N]; |
| 51 | int32_t main() { |
| 52 | map<int, int>mp; |
| 53 | int n, q; |
| 54 | cin >> n >> q; |
| 55 | for(int i = 1; i <= n; i++) cin >> a[i], mp[a[i]]; |
| 56 | int c = 0; |
| 57 | for(auto x : mp) mp[x.first] = ++c, V[c] = x.first; |
| 58 | root[0] = t.build(1, n); |
| 59 | for(int i = 1; i <= n; i++) { |
| 60 | root[i] = t.upd(root[i - 1], 1, n, mp[a[i]], 1); |
| 61 | } |
| 62 | while(q--) { |
| 63 | int l, r, k; |
| 64 | cin >> l >> r >> k; |
| 65 | cout << V[t.query(root[l - 1], root[r], 1, n, k)] << '\n'; |
| 66 | } |
| 67 | return 0; |
| 68 | } |