#include<bits/stdc++.h> using namespace std; #define int long long const int N=3e5+10; int T,n,m,a[N],b[N],c[N],mmax; bool check(int mid){//如果把小于mid的看成0，大于等于mid的看成1，是否可以使1的个数多于m（即第m大是否可以大于等于mid） // cout<<"!!"<<mid<<endl; for(int i=1;i<=n;i++){if(a[i]<mid){b[i]=0;}else{b[i]=1;}} // for(int i=1;i<=n;i++)cout<<b[i]<<" ";cout<<endl; int cnt=0,ans=0,ct_0=0,res=0; //先删0，再删1（如果要删1，换成删离它最近的0不劣） //全是1的处理显然，最后统一处理->只考虑怎么删0 //如果有一段偶数长的1，那么不管怎么删0，贡献都是段长/2；如果是奇数长的1，看作是1个1和一段偶数长的1 for(int i=1;i<=n;){ if(b[i]==0){c[++cnt]=0;i++;ct_0++;} else{ int ct=0,j=i; while(j<=n&&b[j]==1){j++;ct++;res++;} if(ct%2){c[++cnt]=1;res--;} i=j; } } // for(int i=1;i<=cnt;i++)cout<<c[i]<<" ";cout<<endl; //对于一个1，删他前面的某个0的总贡献是0的个数/2（若有奇数个0且一开始它在奇数位上，则要+1） //删他后面的0的贡献至多为0的个数，要达到这一点可以采用如下策略： //先把第一段0删完，后面的每一段0都删成只剩一个，最后再把这些0从左至右依次删掉 int ct=0; for(int i=1;i<=cnt;i++){ if(c[i]==0){ct++;continue;} ans+=ct/2;if((i%2)&&(ct%2))ans++; } ans+=(res/2)*ct_0; ct=0; for(int i=cnt;i>=1;i--){ if(c[i]==0){ct++;continue;} else ans+=ct; } for(int i=n-ct;i>=1;i--){ans+=(i+1)/2;} // cout<<ans<<endl; return ans>=m; } signed main(){ //freopen("T2.in","r",stdin); scanf("%lld",&T); while(T--){ scanf("%lld%lld",&n,&m);mmax=0; for(int i=1;i<=n;i++){scanf("%lld",&a[i]);mmax=max(mmax,a[i]);} //二分答案 int l=1,r=mmax; while(l<r){ int mid=(l+r+1)>>1; if(check(mid)){l=mid;} else r=mid-1; } printf("%lld\n",l); // cout<<endl<<endl<<endl; } return 0; }