#include <bits/stdc++.h> using namespace std; #define int long long #define endl "\n" int n,m; int a[300300]; bool b[300300]; inline bool chk(int lim){ int c[2]; c[0]=c[1]=0; for(int i=1;i<=n;i++) c[b[i]=a[i]>=lim]++; int res=0; vector<int>g; int s=0; int x=0; for(int i=1;i<=n;i++) if(!b[i]){ if(s&1)g.push_back(1),x++; res+=s/2*c[0]; g.push_back(0); s=0; } else s++; if(s&1)g.push_back(1),x++; res+=s/2*c[0]; x=c[1]; // if(lim==3)cout<<res<<" "<<x<<endl; while(x){ res+=(x+1)/2; x--; } int fr=0; int k=g.size(); for(int i=0;i<k;i++) if(!g[i])fr++; else{ int bk=c[0]-fr; res+=bk+fr/2; if(fr%2==1&&i%2==0)res++; } return res>=m; } signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); // freopen("ex_card12.in","r",stdin); // freopen("SS.out","w",stdout); int t; cin>>t; while(t--){ cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; int l=1,r=1e9; while(l<r){ int mid=1+l+r>>1; if(chk(mid))l=mid; else r=mid-1; } cout<<l<<endl; } cout.flush(); return 0; }