K-th Number

K-th Number

突破口：直接考虑最后的B序列是一个由原序列中的数字多次或0次出现构成的序列，那么将B序列排序之后我们发现，对于每个数字出现的位置都有一个L，R，并且数字越小的其实排名越靠后，由这里我们就可以发现，最后的答案是满足二分性质的，所以我们可以直接二分Mst求出mid在B序列中的R即可.
这一部分可以用尺取法，即如果一个数要想对当前mid做出贡献，那么他所在的区间必须有>=k个比mid大的元素，所以将所有>=mid的元素看做一个，然后枚举右端点即可

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
#define yes puts("YES")
#define no puts("NO")
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 3e5 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}

//head
LL _,n,m,k,a[maxn],b[maxn];
bool ok(LL x){
    vector<LL>v;
    for(int i=1;i<=n;i++) if(b[i]>=x) v.pb(i);
    v.pb(n+1);
    int sz=v.size();
    LL ans=0;
    for(int i=0;i<=sz-k-1;i++){
        LL l=v[i],r=v[i+k]-v[i+k-1];
        ans+=l*r;
    }
    return ans>=m;
}

int main(){
    for(scanf("%lld",&_);_;_--){
        scanf("%lld%lld%lld",&n,&k,&m);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]),b[i]=a[i];
        sort(a+1,a+1+n,greater<LL>());
        int l=1,r=n,ans=-1;
        while(l<=r){
            int mid=l+r>>1;
            if(ok(a[mid])) {r=mid-1;ans=mid;}
            else l=mid+1;
        }
        printf("%d\n",a[ans]);
    }

}