#include<bits/stdc++.h>
using namespace std;
const int N=30005;
int t,n;
int d[N],b[N];
int main()
{
freopen("dining.in","r",stdin);
freopen("dining.out","w",stdout);
scanf("%d",&t);
while(t--)
{
memset(b,0,sizeof(b));
int tot=0,ans=0;
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&d[i]);
for(int i=1; i<=n; i++)//每个最长不下降子序列扫一遍
{
int cnt=upper_bound(b+1,b+1+tot,d[i])-b;
if(cnt==tot+1) tot++;
b[cnt]=d[i];
}
ans=max(ans,tot);
memset(b,0,sizeof(b));//注意还原 0
tot=0;
for(int i=n; i>=1; i--)//每个最长不下降子序列扫一遍
{
int cnt=upper_bound(b+1,b+1+tot,d[i])-b;
if(cnt==tot+1) tot++;
b[cnt]=d[i];
}
ans=max(ans,tot);
ans=n-ans;
printf("%d\n",ans);
}
return 0;
}