#include<bits/stdc++.h> #define ll long long using namespace std; const int N=3e5+10,S=1.2e6; int n;ll m; int a[N]; bool b[N],c[N],vis[N]; ll calc(){ ll res=0; int cnt=0; for(int i=1;i<=n;i++){ if(b[i]) cnt++; }for(int i=1;i<=cnt;i++){ res+=(i+1)/2; }int tr=n-cnt; for(int i=1;i<=n;i++){ if(b[i]&&b[i-1]&&(!vis[i-1])) res+=tr,vis[i]=1,vis[i-1]=1; }int tp=0; for(int i=1;i<=n;i++) if(!vis[i]) c[++tp]=b[i]; int c0=0; for(int i=tp;i>=1;i--){ if(!c[i]) c0++; else res+=c0+(tr-c0+(i%2))/2; }return res; }bool chk(int k){ for(int i=1;i<=n;i++) b[i]=(a[i]>=k); //cout<<calc()<<' '<<m<<endl; return (calc()>=m); }void solve(){ int l=1,r=1e9+10; while(l<r){ int mid=(l+r+1)/2; if(chk(mid)) l=mid; else r=mid-1; }cout<<l<<endl; } void slv(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; solve(); } int main(){ int t;cin>>t;while(t--) slv(); return 0; }