输入描述:

第一行一个数n
第二行n个数表示序列a
第三行一个数m
之后m行每行四个数表示l r k1 k2

输出描述:

对于每次询问输出一行一个数表示答案

输入例子:

10

3 6 6 8 3 10 1 6 5 6

10

4 7 1 2

5 7 1 1

5 6 1 2

2 6 2 1

8 9 1 1

6 9 1 2

1 2 1 1

1 4 2 1

5 7 1 3

2 6 1 3

输出例子:

3

1

10

6

5

5

3

6

10

10

-->

10

3 6 6 8 3 10 1 6 5 6

10

4 7 1 2

5 7 1 1

5 6 1 2

2 6 2 1

8 9 1 1

6 9 1 2

1 2 1 1

1 4 2 1

5 7 1 3

2 6 1 3

3

1

10

6

5

5

3

6

10

10

3 6 6 8 3 10 1 6 5 6
[4,7]中出现1次的有1,3,8,10，第2小的是3
[5,7]中出现1次的有1,3,10，第1小的是1
[5,6]中出现1次的有3,10，第2小的是10
[2,6]中出现2次的有6，第1小的是6
[8,9]中出现1次的有5,6，第1小的是5
[6,9]中出现1次的有1,5,6,10，第2小的是5
[1,2]中出现1次的有3,6，第1小的是3
[1,4]中出现2次的有6，第1小的是6
[5,7]中出现1次的有1,3,10，第3小的是10
[2,6]中出现1次的有3,8,10，第3小的是10

备注:

对于100%的数据，
有1<=n,a[i],m<=40000
数据保证一定能找到那个数

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

int read(){

    int x=,f=;char ch=getchar();

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (''<=ch&&ch<='') x=(x<<)+(x<<)+ch-'',ch=getchar();

    return x*f;

}

const int N=;

int n,m,have[N],a[N],ap[N],cnt[N][],cntk[],ans[N],pos,bb,blo,L,R;

//have[i]表示是否有次数为i的值出现

//ap[i]表示值为i的数字出现了几次

//cntk[i]表示有多少个不同数值出现了k次，k处在i块里

//cnt[i][j]表示出现了i次的值里，值处在j块有多少

struct node{

    int l,r,blo,id,k1,k2;

}q[N];

bool operator < (const node &A,const node &B){

    return A.blo<B.blo||A.blo==B.blo&&A.r<B.r;

}

void work(int x,int w){

    int val=a[x],cc=ap[val];

    if (!--have[cc]) cntk[(cc-)/bb+]--;

    cnt[cc][(val-)/bb+]--;

    ap[val]+=w;cc=ap[val];

    if (++have[cc]==) cntk[(cc-)/bb+]++;

    cnt[cc][(val-)/bb+]++; //[次数][值所属的块]

}

int qry(int k1,int k2){

    int i=,j;

    while (k1>cntk[i]) k1-=cntk[i],i++;//sqrt(n),次数所属的块，每个块有多少个出现了

    for (j=(i-)*bb+;j<=i*bb;j++)//sqrt(n)

        if (have[j])

        if (!--k1) break;

    pos=j;i=;//k1小的是j次/pos次

    while (k2>cnt[pos][i]) k2-=cnt[pos][i],i++;//sqrt(n)

    for (j=(i-)*bb+;j<=i*bb;j++)//sqrt(n)

        if (ap[j]==pos)

        if (!--k2) break;

    return j;

}

int main(){

    n=read();bb=(int)sqrt(n);

    for (int i=;i<=n;i++) a[i]=read();

    m=read();blo=(int)sqrt(m);

    for (int i=;i<=m;i++)

        q[i].l=read(),q[i].r=read(),q[i].k1=read(),

        q[i].k2=read(),q[i].id=i,q[i].blo=(q[i].l-)/blo+;

    sort(q+,q+m+);

    L=;R=;

    for (int i=;i<=m;i++)

    {

        while (L>q[i].l) work(--L,);

        while (R<q[i].r) work(++R,);

        while (L<q[i].l) work(L++,-);

        while (R>q[i].r) work(R--,-);

        ans[q[i].id]=qry(q[i].k1,q[i].k2);

    }

    for (int i=;i<=m;i++) printf("%d\n",ans[i]);

    return ;

}