#ifdef __LOCAL
#define _GLIBCXX_DEBUG
#else
#ifdef __GNUC__
#pragma GCC optimize("O3")
#endif
#endif
#include<bits/stdc++.h>
#include<cassert>
using namespace std;
using uint=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=unsigned __int128;
using ld=long double;
#define rep(i,n) for(ll i=0;i<(n);++i)
#define repr(i,n) for(ll i=(n)-1;i>=0;--i)
#define repa(i,a,b) for(ll i=(a);i<(b);++i)
#define repb(i,a,b) for(ll i=(b)-1;i>=(a);--i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define uniq(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
struct ll2{
   ll a,b;
   friend auto operator<=>(const ll2&,const ll2&)=default;
};
struct ll3{
   ll a,b,c;
   friend auto operator<=>(const ll3&,const ll3&)=default;
};
struct ll4{
   ll a,b,c,d;
   friend auto operator<=>(const ll4&,const ll4&)=default;
};
struct ll5{
   ll a,b,c,d,e;
   friend auto operator<=>(const ll5&,const ll5&)=default;
};
struct ll6{
   ll a,b,c,d,e,f;
   friend auto operator<=>(const ll6&,const ll6&)=default;
};
struct frac{
   ll a,b;
   friend auto operator<=>(frac a,frac b){
      if(a.b==0&&b.b==0){
         if(a.a>0&&b.a>0)return 0;
         if(a.a<0&&b.a<0)return 0;
         if(a.a>0&&b.a<0)return -1;
         return 1;
      }
      if(a.b==0&&a.a>0)return -1;
      if(b.b==0&&b.a>0)return 1;
      if(a.b>=0&&b.b<=0)return -1;
      if(a.b<=0&&b.b>=0)return 1;
      if(a.a*b.b<a.b*b.a)return 1;
      if(a.a*b.b==a.b*b.a)return 0;
      return -1;
   }
};
constexpr ll MOD=998244353LL;
constexpr ll MOD2=1000000007LL;
constexpr ll IMOD=11451445450721LL;
constexpr ll B10=1024LL;
constexpr ll B20=1048576LL;
constexpr ll B30=1073741824LL;
constexpr ll B40=1099511627776LL;
constexpr ll B50=1125899906842624LL;
constexpr ll B60=1152921504606846976LL;
constexpr ll INF=B60;
constexpr ll E3=1000LL;
constexpr ll E4=10000LL;
constexpr ll E5=100000LL;
constexpr ll E6=1000000LL;
constexpr ll E7=10000000LL;
constexpr ll E8=100000000LL;
constexpr ll E9=1000000000LL;
constexpr ll E10=10000000000LL;
constexpr ll E11=100000000000LL;
constexpr ll E12=1000000000000LL;
constexpr ll E13=10000000000000LL;
constexpr ll E14=100000000000000LL;
constexpr ll E15=1000000000000000LL;
constexpr ll E16=10000000000000000LL;
constexpr ll E17=100000000000000000LL;
constexpr ll E18=1000000000000000000LL;
constexpr ll2 D2[]={{0,1},{1,0}};
constexpr ll2 D4[]={{-1,0},{0,-1},{1,0},{0,1}};
constexpr ll2 D8[]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
constexpr char ALPH[]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
constexpr char alph[]="abcdefghijklmnopqrstuvwxyz";
istream&operator>>(istream&is,i128&x){
   ll y;is>>y;x=y;
   return is;
}
ostream&operator<<(ostream&os,i128&x){
   os<<static_cast<ll>(x);
   return os;
}
ostream&operator<<(ostream&os,const ll2&o){
   os<<o.a<<' '<<o.b;
   return os;
}
ostream&operator<<(ostream&os,const ll3&o){
   os<<o.a<<' '<<o.b<<' '<<o.c;
   return os;
}
ostream&operator<<(ostream&os,const ll4&o){
   os<<o.a<<' '<<o.b<<' '<<o.c<<' '<<o.d;
   return os;
}
ostream&operator<<(ostream&os,const ll5&o){
   os<<o.a<<' '<<o.b<<' '<<o.c<<' '<<o.d<<' '<<o.e;
   return os;
}
ostream&operator<<(ostream&os,const ll6&o){
   os<<o.a<<' '<<o.b<<' '<<o.c<<' '<<o.d<<' '<<o.e<<' '<<o.f;
   return os;
}
// Print Vector
template<class T>
ostream&operator<<(ostream&os,const vector<T>&V){
   for(auto a:V)os<<a<<' ';
   return os;
}
// Print Set
template<class T>
ostream&operator<<(ostream&os,const set<T>&V){
   for(auto a:V)os<<a<<' ';
   return os;
}
// Print MultiSet
template<class T>
ostream&operator<<(ostream&os,const multiset<T>&V){
   for(auto a:V)os<<a<<' ';
   return os;
}
// Chmax
template<class T>
bool cmax(T&a,T b){
   if(a<b){a=b;return 1;}
   return 0;
}
// Chmin
template<class T>
bool cmin(T&a,T b){
   if(a>b){a=b;return 1;}
   return 0;
}
// Safe Division
ll dv(ll x,ll y){
   if(x>0)return x/y;
   return (x+((-x)/y+1)*y)/y-((-x)/y+1);
}
// Safe Mod
ll md(ll x,ll y){return x-y*dv(x,y);}
// Add and Mod
void madd(ll&a,ll b,ll mod=MOD){a=(md(a,mod)+md(b,mod))%mod;}
// Multiply and Mod
void mmul(ll&a,ll b,ll mod=MOD){a=md(a,mod)*md(b,mod)%mod;}
// Mod Power
ll mpow(ll x,ll y,ll mod=MOD){
   if(y==0)return 1%mod;
   ll t=mpow(x,y>>1,mod);
   if(y&1)return t*t%mod*x%mod;
   return t*t%mod;
}
// Extended GCD
ll2 egcd(ll a,ll b,ll t=1){
   if(a>b){
      auto[x,y]=egcd(b,a,t);
      return {x,y};
   }
   if(!a)return {0,t/b};
   auto[x,y]=egcd(b%a,a,t);
   return {y-b/a*x,x};
}
// Mod Inversion
ll minv(ll x,ll mod=MOD){return md(egcd(x,mod).a,mod);}
// Identity Matrix
vector<vector<ll>> imat(ll n,ll mod=MOD){
   vector X(n,vector<ll>(n,0));
   rep(i,n)X[i][i]=1%mod;
   return X;
}
// Matrix Prod
vector<vector<ll>> mtpr(vector<vector<ll>> X,vector<vector<ll>> Y,ll mod=MOD){
   vector Z(X.size(),vector<ll>(Y[0].size(),0));
   rep(i,X.size())rep(j,Y.size())rep(k,Y[0].size())Z[i][k]=(Z[i][k]+X[i][j]*Y[j][k])%mod;
   return Z;
}
// Matrix Power
vector<vector<ll>> mtpw(vector<vector<ll>> X,ll n,ll mod=MOD){
   if(!n)return imat(X.size(),mod);
   if(n%2)return mtpr(mtpw(X,n-1,mod),X,mod);
   auto Y=mtpw(X,n/2,mod);
   return mtpr(Y,Y,mod);
}
// Factorial
pair<vector<ll>,vector<ll>> fact(ll n,ll mod=MOD,bool inv=true){
   vector<ll> ans(n+1,1),ians(n+1);
   rep(i,n)ans[i+1]=ans[i]*(i+1)%mod;
   ians[n]=minv(ans[n],mod);
   repr(i,n)ians[i]=ians[i+1]*(i+1)%mod;
   return {ans,ians};
}
// Combination
ll comb(const vector<ll>&fct,const vector<ll>&ifct,ll n,ll r,ll mod=MOD){
   if(r<0||n<r||n<0)return 0;
   return fct[n]*ifct[r]%mod*ifct[n-r]%mod;
}
// Divisors
vector<ll> divs(ll n){
   vector<ll> ans;
   repa(i,1,static_cast<ll>(sqrt(static_cast<double>(n)))+1){
      if(n%i==0){
         ans.push_back(i);
         if(i!=n/i)ans.push_back(n/i);
      }
   }
   return ans;
}
// BFS
void bfs(const vector<vector<ll>>&G,vector<ll>&M,vector<ll> st){
   queue<ll> Q;
   for(ll s:st){
      Q.push(s);
      M[s]=0;
   }
   while(!Q.empty()){
      ll p=Q.front();Q.pop();
      for(ll q:G[p]){
         if(M[p]+1<M[q]){
            M[q]=M[p]+1;
            Q.push(q);
         }
      }
   }
}
// BFS with Parents
void bfsp(const vector<vector<ll>>&G,vector<ll>&M,vector<ll>&P,vector<ll> st){
   queue<ll> Q;
   for(ll s:st){
      Q.push(s);
      M[s]=0;
   }
   while(!Q.empty()){
      ll p=Q.front();Q.pop();
      for(ll q:G[p]){
         if(M[p]+1<M[q]){
            M[q]=M[p]+1;
            P[q]=p;
            Q.push(q);
         }
      }
   }
}
// 0-1BFS
void bfs1(const vector<vector<ll2>>&G,vector<ll>&M,vector<ll> st){
   deque<ll> Q;
   for(ll s:st){
      Q.push_back(s);
      M[s]=0;
   }
   while(!Q.empty()){
      ll p=Q.front();Q.pop_front();
      for(auto[d,q]:G[p]){
         if(M[p]+d<M[q]){
            M[q]=M[p]+d;
            if(d==1)Q.push_back(q);
            else Q.push_front(q);
         }
      }
   }
}
// Bellman-Ford
vector<ll> bf(ll n,const vector<ll3>&E,vector<ll> st){
   vector<ll> dis(n,INF);
   for(ll s:st)dis[s]=0;
   rep(i,n)for(auto[w,u,v]:E)if(dis[v]>dis[u]+w)dis[v]=dis[u]+w;
   for(auto[w,u,v]:E)if(dis[v]>dis[u]+w){
      rep(i,n)dis[i]=-INF;
      return dis;
   }
   return dis;
}
// Dijkstra
vector<ll> dij(const vector<vector<ll2>>&G,vector<ll> st){
   ll n=G.size();
   priority_queue<ll2,vector<ll2>,greater<>> Q;
   vector<ll> dis(n,INF);
   for(ll s:st){
      Q.emplace(0,s);
      dis[s]=0;
   }
   while(!Q.empty()){
      auto[d,p]=Q.top();Q.pop();
      if(d>dis[p])continue;
      for(auto[e,q]:G[p]){
         if(d+e<dis[q]){
            dis[q]=d+e;
            Q.emplace(d+e,q);
         }
      }
   }
   return dis;
}
// Warshall-Floyd
vector<vector<ll>> wf(const vector<vector<ll>>&G){
   ll n=G.size();
   vector dis(n,vector<ll>(n));
   rep(i,n){
      rep(j,n)dis[i][j]=G[i][j];
      dis[i][i]=0;
   }
   rep(k,n)rep(i,n)rep(j,n)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
   return dis;
}
// Tree Diamiter
ll3 td(const vector<vector<ll>>&G){
   ll n=G.size();
   vector<ll> M1(n,INF);
   bfs(G,M1,{0});
   ll mx=-1,st;
   rep(i,n)if(M1[i]>mx){
      mx=M1[i];
      st=i;
   }
   vector<ll> M2(n,INF);
   bfs(G,M2,{st});
   mx=-1;ll gl;
   rep(i,n)if(M2[i]>mx){
      mx=M2[i];
      gl=i;
   }
   return {mx,st,gl};
}
// Union-Find
struct uf{
   vector<ll> par;
   explicit uf(ll n):par(n,-1){}
   ll find(ll u){
      vector<ll> A;
      while(par[u]>=0){
         A.push_back(u);
         u=par[u];
      }
      rep(i,A.size())par[A[i]]=u;
      return u;
   }
   bool same(ll u,ll v){return find(u)==find(v);}
   void merge(ll u,ll v){
      u=find(u);
      v=find(v);
      if(u==v)return;
      if(par[u]>par[v])swap(u,v);
      par[u]+=par[v];
      par[v]=u;
   }
};
// Weighted Union-Find
struct wuf{
   vector<ll> par;
   vector<ll> dif;
   explicit wuf(ll n):par(n,-1),dif(n){}
   ll2 find(ll u){
      vector<ll> A;
      ll dis=0;
      while(par[u]>=0){
         A.push_back(u);
         dis+=dif[u];
         u=par[u];
      }
      ll sum=dis;
      rep(i,A.size()){
         par[A[i]]=u;
         sum-=dif[A[i]];
         dif[A[i]]+=sum;
      }
      return {u,dis};
   }
   bool same(ll u,ll v){return find(u).a==find(v).a;}
   void merge(ll u,ll v,ll w){
      auto[ur,ud]=find(u);
      auto[vr,vd]=find(v);
      if(ur==vr)return;
      if(par[ur]>par[vr]){
         swap(ur,vr);
         w=-w;ud=-ud;vd=-vd;
      }
      par[ur]+=par[vr];
      par[vr]=ur;
      dif[vr]=w+ud-vd;
   }
   ll diff(ll u,ll v){return find(v).b-find(u).b;}
};
// Coordinate Compression
vector<ll> comp(const vector<ll>&A){
   ll n=A.size();
   set<ll> S;
   for(ll a:A)S.insert(a);
   vector<ll> T;
   for(ll s:S)T.push_back(s);
   vector<ll> ans(n);
   rep(i,n)ans[i]=distance(T.begin(),lower_bound(all(T),A[i]));
   return ans;
}
// MST
vector<ll3> mst(ll n,const vector<ll3>&E){
   vector<ll3> F=E;sort(all(F));
   uf U(n);
   vector<ll3> ans;
   for(auto[w,u,v]:F){
      if(!U.same(u,v)){
         U.merge(u,v);
         ans.emplace_back(w,u,v);
      }
   }
   return ans;
}
// Bipartite Coloring
vector<ll> bip(const vector<vector<ll>>&G){
   ll n=G.size();
   vector<ll> ans(n,-1);
   bool ok=true;
   rep(i,n){
      if(ans[i]==-1){
         ans[i]=0;
         queue<ll> Q({i});
         while(!Q.empty()){
            ll p=Q.front();Q.pop();
            for(ll q:G[p]){
               if(ans[q]==-1){
                  ans[q]=ans[p]^1;
                  Q.push(q);
               }else if(ans[q]==ans[p])ok=false;
            }
         }
      }
   }
   if(!ok)ans[0]=-1;
   return ans;
}
// Lowlink
pair<vector<ll>,vector<ll>> lowl(const vector<vector<ll>>&G,ll s){
   ll n=G.size();
   vector<ll> dis(n,-1),low(n);
   dis[s]=0;
   ll c=1;
   auto dfs=[&](auto&&dfs,ll x)->ll{
      for(ll y:G[x]){
         if(dis[y]==-1){
            dis[y]=c;low[y]=c;++c;
            dfs(dfs,y);
            low[x]=min(low[x],low[y]);
         }else if(dis[y]<dis[x]-1)low[x]=min(low[x],dis[y]);
      }
      return 0;
   };
   dfs(dfs,s);
   return {dis,low};
}
// Map with Default Value
template<class S,class T>
struct dmap:map<S,T>{
   T def;
   explicit dmap(T def):def(def){}
   T&operator[](const S&i){return map<S,T>::emplace(i,def).first->second;}
};
// Min-Plus Convolution
vector<ll> mpc(vector<ll> X,vector<ll> Y){
   vector<ll> R={X[0]+Y[0]};
   ll a=0,b=0;while(1){
      ll t=1;if(a==X.size()-1){
         if(b==Y.size()-1)break;
         else t=0;
      }else{
         if(b<Y.size()-1&&X[a+1]-X[a]>Y[b+1]-Y[b])t=0;
      }if(t){R.push_back(R.back()+X[a+1]-X[a]);++a;}
      else{R.push_back(R.back()+Y[b+1]-Y[b]);++b;}
   }return R;
}
namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder
namespace atcoder {

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder
ll op(ll x,ll y){return max(x,y);}
ll e(){return -INF;}
ll slv(ll n,vector<ll> A){
   A=comp(A);rep(i,n)++A[i];//cout<<A<<endl;
   atcoder::segtree<ll,op,e> S(n+2),T(n+2),U(n+2),V(n+2),W(n+2);
   S.set(n+1,0);S.set(A[0],1);repa(i,1,n){
      ll t1=max(S.prod(A[i]+1,n+2),T.prod(A[i]+1,n+2))+1;
      ll t2=max(S.prod(1,n+2),T.prod(1,n+2));
      ll u1=max(T.prod(0,A[i]),U.prod(0,A[i]))+1;
      ll u2=max(T.prod(0,n+1),U.prod(0,n+1));
      ll v1=max(U.prod(A[i]+1,n+2),V.prod(A[i]+1,n+2))+1;
      ll v2=max(U.prod(1,n+2),V.prod(1,n+2));
      ll w1=max(V.prod(0,A[i]),W.prod(0,A[i]))+1;
      ll w2=max(V.prod(0,n+1),W.prod(0,n+1));
      T.set(A[i],t1);T.set(0,t2);
      U.set(A[i],u1);U.set(n+1,u2);
      V.set(A[i],v1);V.set(0,v2);
      W.set(A[i],w1);W.set(n+1,w2);
   }return n-W.all_prod();
}
int main(){
   cin.tie(0)->sync_with_stdio(0);
   ll t;cin>>t;while(t--){
   ll n;cin>>n;
   vector<ll> A(n);rep(i,n)cin>>A[i];
   cout<<slv(n,A)<<'\n';}
}