枚举每个人，计算他必定是诚实者的情况下至少有几个人说谎，若超过$t$则他肯定是说谎者。
对于至少有几个人说谎，区间信息可以合并：
每个区间维护最左最右两个人$l,r$以及$f[i][j]$表示$l$和$r$诚实说谎状态分别为$i,j$时他们之间至少几个人说谎。
利用前缀和、后缀和可以在$O(1)$时间内求出每个人必定诚实时至少有几个人说谎。
时间复杂度$O(n)$。
#include<cstdio>
#define rep(i) for(int i=0;i<2;i++)
const int N=100010,inf=100000000;
inline void up(int&a,int b){a>b?(a=b):0;}
int Case,n,m,i,ans,mi,a[N];
struct P{
int l,r,f[2][2];
void set(int x){
l=r=x;
rep(i)rep(j)f[i][j]=inf;
f[0][0]=0;
f[1][1]=1;
}
void must(int x){
l=r=x;
rep(i)rep(j)f[i][j]=inf;
f[0][0]=0;
}
P operator+(const P&b){
P c;
c.l=l,c.r=b.r;
rep(i)rep(j)c.f[i][j]=inf;
rep(i)rep(j)if(f[i][j]<inf)rep(x)rep(y)if(b.f[x][y]<inf){
if(!j&&a[r]!=x)continue;
up(c.f[i][y],f[i][j]+b.f[x][y]);
}
return c;
}
}pre[N],suf[N],e[N],tmp;
int main(){
scanf("%d",&Case);
while(Case--){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&a[i]),e[i].set(i);
for(pre[1]=e[1],i=2;i<=n;i++)pre[i]=pre[i-1]+e[i];
for(suf[n]=e[n],i=n-1;i;i--)suf[i]=e[i]+suf[i+1];
for(ans=mi=0,i=n;i;i--){
e[i].must(i);
tmp=e[i];
if(i<n)tmp=tmp+suf[i+1];
if(i>1)tmp=tmp+pre[i-1];
tmp=tmp+e[i];
if(tmp.f[0][0]>m)ans++,mi=i;
}
printf("%d %d\n",ans,mi);
}
return 0;
}