#include<iostream> #include<ctime> #define timeMS (clock()*1000/CLOCKS_PER_SEC) using namespace std; const int N=500100,LG=20; inline int read(){ int i=getchar(),r=0,s=1; while(i<'0'||i>'9'){if(i=='-')s=-1;i=getchar();} while(i>='0'&&i<='9')r=(r<<1)+(r<<3)+(i^48),i=getchar(); return r*s; } int n,k,a[N],mx[LG][N],mn[LG][N],lg[N]; void init(){ cin>>n>>k; for(int i=1;i<=n;i++)a[i]=mx[0][i]=mn[0][i]=read(); for(int i=1;i<=lg[n];i++){ for(int j=1;j+(1<<i)-1<=n;j++){ mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<(i-1))]); mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<(i-1))]); } } } inline int get_max(int l,int r){ int len=r-l+1; return max(mx[lg[len]][l],mx[lg[len]][r-(1<<lg[len])+1]); } inline int get_min(int l,int r){ int len=r-l+1; return min(mn[lg[len]][l],mn[lg[len]][r-(1<<lg[len])+1]); } inline int range(int l,int r){return get_max(l,r)-get_min(l,r);} int f[N],cnt[N]; inline int check(int lim){ f[0]=1; for(int i=1;i<=n;i++){ f[i]=f[i-1]; while(f[i]<=n&&range(i,f[i])<lim)f[i]++; } int res=0,sum=0; for(int i=1;i<=n;i++){ if(f[i]<=n&&f[i]-i+1<=n-i+1)cnt[f[i]-i+1]++,sum++; if(sum>=k)res=n-i+1; sum-=cnt[n-i+1]; } for(int i=1;i<=n;i++)cnt[i]=0; return res; } using ll=long long; inline int get_ans(ll l,ll r){ while(l<r){ ll mid=(l+r+1)>>1; if(check(mid))l=mid; else r=mid-1; } return l; } signed main(){ // freopen("choose.in","r",stdin); // freopen("choose.out","w",stdout); for(int i=2;i<N;i++)lg[i]=lg[i>>1]+1; int t;cin>>t; while(t--){ init(); int m=range(1,n-k+1); for(int i=1;i<=k;i++)m=min(m,range(i,i+n-k)); int ans=get_ans(m,range(1,n)); printf("%lld %lld\n",ans,check(ans)); } cerr<<timeMS<<endl; return 0; }