#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int t,n,a[N+5],sta[21][N+5],sti[21][N+5],cnt,nw,ans,tz[N+5],b[N+5],ma[N+5],mi[N+5],tp;
int inline g_max(int l,int r){
  int x=log2(r-l+1);
  return max(sta[x][l],sta[x][r-(1<<x)+1]);
}
int inline g_min(int l,int r){
  int x=log2(r-l+1);
  return min(sti[x][l],sti[x][r-(1<<x)+1]);
}
bool inline pj(int l,int r,int l2,int r2){
	return (r+1==l2)||(r2+1==l);
}
int qwq,T;
bool inline check(int l,int r){if(T==10&&n==10000)cout<<l<<" "<<r<<"qwq"<<"\n";
	qwq+=r-l+1;
	if(qwq>=1000000)exit(0);
	tp=0;
  for(int i=l;i<=r;i++)b[i-l+1]=a[i];
  sort(b+1,b+r-l+1+1);
  for(int i=1;i<=r-l+1;i++)tz[b[i]]=i;
  for(int i=l;i<=r;i++){
  tp++;
  ma[tp]=mi[tp]=tz[a[i]];
  while(tp>1&&pj(mi[tp],ma[tp],mi[tp-1],ma[tp-1])){tp--;mi[tp]=min(mi[tp],mi[tp+1]);ma[tp]=max(ma[tp],ma[tp+1]);}
  }
  return (tp==1);
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  cin>>t;T=t;
  while(t--){
  cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i];
  nw=1;ans=0;
  for(;nw<=n;){cnt=0;
  for(int i=1;i<=n-nw+1;i<<=1)
  if(check(nw,nw+i-1))cnt=i;
  int l=0,r=min(n-cnt-nw+1,cnt-1);
  while(l<r){
  int mid=l+r+1>>1;
  if(check(nw,nw+cnt+mid-1))l=mid;
  else r=mid-1;
  }
  nw=nw+cnt+l;
  ans++;
  }
  cout<<n-ans<<"\n";
  }
}