#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） for(int i=1;i<=n;i++){if(a[i]<mid){b[i]=0;}else{b[i]=1;}} int cnt=0,ans=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++;} else{ int ct=1,j=i+1; while(j<=n&&b[j]==1){j++;ct++;} if(ct%2)c[++cnt]=0; i=j+1; } } //对于一个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)ans++; } ct=0; for(int i=cnt;i>=1;i--){ if(c[i]==0){ct++;continue;} ans+=ct; } for(int i=n-ct;i>=1;i--)ans+=(i+1)/2; return ans>=m; } signed main(){ 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); } return 0; }