#include <bits/stdc++.h>
using namespace std;
int main()
{
   ios::sync_with_stdio(0);
   int T = 1; cin >> T;
   while(T--)
   {
      int n; cin >>n;
      vector <int> p(n+1), d(n+1), pos(n+1);
      for(int i=1;i<=n;++i) cin >>p[i],pos[p[i]]=i;
      if(n==1){cout<<0<<'\n';continue;}
      for(int i=1;i<=n;++i)
         d[p[i]] = d[p[i]-1]+1;
      int ans= 0;
      for(int i=n/2;i>=1;--i)
         if(d[n+1-i]<(n+1-i)-i+1)
            ++ans;
      cout<<ans<<'\n';
   }
   return 0;
}