#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
int n, m, cnt, root[N], a[N];
int ls[N << 5], rs[N << 5], w[N << 5];
vector<int> b;
int update(int lu, int l, int r, int x) {
int u = ++cnt;
ls[u] = ls[lu]; rs[u] = rs[lu]; w[u] = w[lu] + 1;
if (l == r) return u;
int mid = (l + r) >> 1;
if (x <= mid) ls[u] = update(ls[lu], l, mid, x);
else rs[u] = update(rs[lu], mid + 1, r, x);
return u;
}
// 核心变化:前缀和相减,二分找第 K 小
int query(int u1, int u2, int l, int r, int k) {
if (l == r) return l;
int d = w[ls[u2]] - w[ls[u1]];
int mid = (l + r) >> 1;
if (k <= d) return query(ls[u1], ls[u2], l, mid, k);
else return query(rs[u1], rs[u2], mid + 1, r, k - d);
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
b.push_back(a[i]);
}
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
int max_val = b.size();
for (int i = 1; i <= n; i++) {
int x = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
root[i] = update(root[i - 1], 1, max_val, x);
}
while (m--) {
int l, r, k;
cin >> l >> r >> k;
int ans_rk = query(root[l - 1], root[r], 1, max_val, k);
cout << b[ans_rk - 1] << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}#include<iostream>
#include<stack>
#include<string>
#include<set>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
//#define int long long
const int N=1e6+5;
int n,m,cnt,root[N],last[N];
int ls[N<<5],rs[N<<5],w[N<<5];
int update(int lu,int l,int r,int x){
int u=++cnt;
ls[u]=ls[lu],rs[u]=rs[lu],w[u]=w[lu];w[u]++;
if(l==r)return u;
int mid=(l+r)>>1;
if(x<=mid)ls[u]=update(ls[lu],l,mid,x);
else rs[u]=update(rs[lu],mid+1,r,x);
return u;
}
int query(int u1,int u2,int l,int r,int x){
if(l>=x)return 0;
if(r<x)return w[u2]-w[u1];
int mid=(l+r)>>1;
return query(ls[u1],ls[u2],l,mid,x)+query(rs[u1],rs[u2],mid+1,r,x);
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
if(last[x])root[i]=update(root[i-1],0,n,last[x]);
else root[i]=update(root[i-1],0,n,0);
last[x]=i;
}
cin>>m;
while(m--){
int l,r;
cin>>l>>r;
cout<<query(root[l-1],root[r],0,n,l)<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
while(T--)solve();
}
/*
*/#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
using namespace std;
const int N = 2e5 + 5;
int n, q, cnt, root[N];
int ls[N * 40], rs[N * 40], min_pos[N * 40];
int update(int pre, int l, int r, int x, int pos) {
int u = ++cnt;
ls[u] = ls[pre]; rs[u] = rs[pre];
if (l == r) {
min_pos[u] = pos;
return u;
}
int mid = (l + r) >> 1;
if (x <= mid) ls[u] = update(ls[pre], l, mid, x, pos);
else rs[u] = update(rs[pre], mid + 1, r, x, pos);
min_pos[u] = min(min_pos[ls[u]], min_pos[rs[u]]);
return u;
}
int query(int u, int l, int r, int limit_L) {
if (l == r) return l;
int mid = (l + r) >> 1;
if (min_pos[ls[u]] < limit_L) return query(ls[u], l, mid, limit_L);
else return query(rs[u], mid + 1, r, limit_L);
}
void solve() {
cin >> n >> q;
for (int i = 1, x; i <= n; ++i) {
cin >> x;
if (x > n + 1) {
root[i] = root[i - 1];
} else {
root[i] = update(root[i - 1], 0, n + 1, x, i);
}
}
while (q--) {
int l, r;
cin >> l >> r;
cout << query(root[r], 0, n + 1, l) << '\n';
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
return 0;
}