#include<stdio.h>
#include<algorithm>
#include<numeric>
constexpr int N{100000};
int a[N+5],b[N+5],p[N+5];
struct segment {
    int l,r;
    constexpr segment():l{},r{} {}
    constexpr segment(const int &v):l{v},r{v} {}
    constexpr bool adjacent_to(const segment &x) const {
        return r+1==x.l||x.r+1==l;
    }
    constexpr void include(const segment &x) {
        l=std::min(l,x.l),r=std::max(r,x.r);
    }
};
segment seg[N+5];
int vis[N+5];
int pre[N+5],nxt[N+5];
int que[(N<<1)+5];
void solve() {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",a+i);
    }
    const auto check([&](const int &l,const int &r)->bool {
        if(l==r) {
            return true;
        }
        const int len{r-l+1};
        std::copy(a+l,a+r+1,b+1);
        std::sort(b+1,b+len+1);
        for(int i=l;i<=r;i++) {
            seg[i]=p[i]=std::lower_bound(b+1,b+len+1,a[i])-b;
        }
        std::fill(vis+l,vis+r+1,0);
        std::iota(pre+l,pre+r+1,l-1),pre[l-1]=l-1;
        std::iota(nxt+l,nxt+r+1,l+1),nxt[r+1]=r+1;
        int cnt{0};
        int qb{1},qe{0};
        const auto try_insert([&](const int &x)->void {
            if(seg[x].adjacent_to(seg[nxt[x]])) {
                que[++qe]=x;
            }
        });
        for(int i=l;i<r;i++) {
            try_insert(i);
        }
        while(qb<=qe) {
            int &u{que[qb++]};
            if(!vis[u]&&seg[u].adjacent_to(seg[nxt[u]])) {
                ++cnt;
                seg[u].include(seg[nxt[u]]);
                vis[nxt[u]]=1;
                pre[nxt[nxt[u]]]=u;
                nxt[u]=nxt[nxt[u]];
                if(pre[u]>=l) {
                    try_insert(pre[u]);
                }
                if(nxt[u]<=r) {
                    try_insert(u);
                }
            }
        }
        return cnt==len-1;
    });
    int ans{0};
    for(int i=1;i<=n;) {
        int len{1};
        while(i+len-1<n&&check(i,std::min(i+(len<<1)-1,n))) {
            len<<=1;
        }
        int l{i+len},r{std::min(i+(len<<1)-1,n)};
        while(l<=r) {
            int mid{l+r>>1};
            if(check(i,mid)) {
                l=mid+1;
            }
            else {
                r=mid-1;
            }
        }
        ++ans,i=l;
    }
    printf("%d\n",n-ans);
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        solve();
    }
    return 0;
}