一看到这道题，我就知道是

替罪羊树上用sb块状链表维护Toptree上的最小费用最大流和可持久化仙人掌，算出来在基尔霍夫矩阵中反演后跑一遍fft维护的插头DP（雾）

看着楼下各种暴力大佬，我深感

我太菜了

只会用

莫队 套 splay

乱搞

时间复杂度： $O(n$√$nlogn)$

空间复杂度： $O(n)$

和主席树相比，时间复杂度多了一个 √$n$

但这支持单点修改！

于是用带修改的莫队就可以做动态区间k大了

做法：

莫队分块暴力修改到当前询问的区间，然后直接splay查询第k大就行了

于是潇潇洒洒随手一敲233行代码

代码：

#include<bits/stdc++.h>
#define N 200005
using namespace std;

int w[N],l=1,r,p[N];
int n,m,sz,root,B;
struct nd
{
    int id,l,r,k,ans;
}a[N];
int f[N],key[N],cnt[N],size[N],ch[N][2];

inline void read(int &x)
{
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) ch=getchar(),w|=ch=='-';
    while( isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}

inline int get(int x)
{
    return ch[f[x]][1]==x;
}

inline void clear(int x)
{
    size[x]=ch[x][1]=ch[x][0]=f[x]=cnt[x]=key[x]=0;
}

inline void update(int x)
{
    if(!x) return ;
    size[x]=cnt[x];
    if(ch[x][0]) size[x]+=size[ch[x][0]];
    if(ch[x][1]) size[x]+=size[ch[x][1]];
}

inline void rotate(int x)
{
    int old=f[x];
    int old_f=f[old];
    int k=get(x);

    ch[old][k]=ch[x][k^1];
    f[ch[old][k]]=old;

    ch[x][k^1]=old;
    f[old]=x;
    f[x]=old_f;

    if(old_f)
        ch[old_f][ch[old_f][1]==old]=x;

    update(old);
    update(x);
}

inline int splay(int x)
{
    for(int fa;(fa=f[x]);rotate(x))
        if(f[fa])
            rotate(get(x)==get(fa)?fa:x);
    root=x;
}

inline int find(int v)
{
    int ans=0,now=root;
    while(1)
    {
        if(v<key[now])
            now=ch[now][0];
        else
        {
            if(ch[now][0])
                ans+=size[ch[now][0]];
            if(v==key[now])
            {
                splay(now);
                return ans+1;
            }
            ans+=cnt[now];
            now=ch[now][1];
        }
    }
}

inline int find_kth(int x)
{
    int now=root;
    while(1)
    {
        if(ch[now][0]&&x<=size[ch[now][0]])
            now=ch[now][0];
        else
        {
            int t=cnt[now];
            if(ch[now][0])
                t+=size[ch[now][0]];
            if(x<=t) return key[now];
            x-=t;
            now=ch[now][1];

        }
    }
}

inline void insert(int v)
{
    if(!root)
    {
        root=++sz;
        key[sz]=v;
        cnt[sz]=size[sz]=1;
        ch[sz][0]=ch[sz][1]=f[sz]=0;
        return ;
    }
    int now=root,fa=0;
    while(1)
    {
        if(key[now]==v)
        {
            cnt[now]++;
            update(now);
            update(fa);
            splay(now);
            return ;
        }
        fa=now;
        now=ch[now][key[now]<v];
        if(now==0)
        {
            f[++sz]=fa;
            key[sz]=v;
            cnt[sz]=size[sz]=1;
            ch[sz][0]=ch[sz][1]=0;
            ch[fa][key[fa]<v]=sz;
            update(fa);
            splay(sz);
            return ;
        }
    }
}

inline int pre()
{
    int now=ch[root][0];
    while(ch[now][1])
        now=ch[now][1];
    return now;
}

inline int next()
{
    int now=ch[root][1];
    while(ch[now][0])
        now=ch[now][0];
    return now;
}

inline void del(int v)
{
    int pp=find(v);
    int x=root;
    if(cnt[x]>1) {cnt[x]--;return ;}
    if(!ch[x][0]&&!ch[x][1]){clear(x);root=0;return ;}
    if(!ch[x][0])
    {
        root=ch[x][1];
        f[root]=0;
        clear(x);
        return ;
    }
    if(!ch[x][1])
    {
        root=ch[x][0];
        f[root]=0;
        clear(x);
        return ;
    }
    int prev=pre();
    splay(prev);
    f[ch[x][1]]=root;
    ch[root][1]=ch[x][1];
    clear(x);
    update(root);
}

bool cmp(nd a,nd b)
{
    return a.l/B==b.l/B ? a.r<b.r:a.l<b.l;
}
bool fcmp(nd a,nd b)
{
    return a.id<b.id;
}

void add(int x,int i)
{
    if(i==1) insert(w[x]);
    else del(w[x]);
}
void work()
{
    for(int i=1;i<=m;i++)
    {
        while(l<=r+1)
        {
            if(l==a[i].l and r==a[i].r) break;
            while(r<a[i].r) add(++r, 1);
    	    while(r>a[i].r) add(r--,-1);
    	    while(l<a[i].l) add(l++,-1);
    	    while(l>a[i].l) add(--l, 1);
        }
        a[i].ans=find_kth(a[i].k);
    }
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++)
        read(w[i]),p[w[i]]=i;
    read(m);B=sqrt(m);
    for(int i=1;i<=m;i++)
        read(a[i].l),read(a[i].r),read(a[i].k),a[i].id=i;
    sort(a+1,a+1+m,cmp);
    work();
    sort(a+1,a+1+m,fcmp);
    for(int i=1;i<=m;i++)
        printf("%d\n",p[a[i].ans]);
    return 0;
}