#include<bits/stdc++.h>
#define int long long int
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=1e6+5;
const int inf=1e18;
int tt=1;
int n,a[maxn];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    set<array<int,3>>p,pp;
    for(int i=1;i<=n;i++)
    {
        p.insert({a[i],i,i});
        pp.insert({i,i,a[i]});
    }
    int ans=0;
    while((int)p.size()>1)
    {
        auto p1=p.begin();
        array<int,3>pp1=*p1;
        auto q1=pp.find({pp1[1],pp1[2],pp1[0]});
        array<int,3> qq1=*q1;
        if(q1==pp.begin())
        {
            auto  q2=q1;++q2;
            array<int,3>qq2=*q2;
            auto p2=p.find({qq2[2],qq2[0],qq2[1]});
            array<int,3>pp2=*p2;
            p.erase(p1);p.erase(p2);
            pp.erase(q1);pp.erase(q2);
            if(pp1[0]!=pp2[0])
            ans+=pp1[2]-pp1[1]+1;
            p.insert({pp2[0],pp1[1],pp2[2]});
            pp.insert({pp1[1],pp2[2],pp2[0]});
        }
        else
        {
            auto  q2=q1;--q2;
            array<int,3>qq2=*q2;
            auto p2=p.find({qq2[2],qq2[0],qq2[1]});
            array<int,3>pp2=*p2;
            p.erase(p1);p.erase(p2);
            pp.erase(q1);pp.erase(q2);
            if(pp1[0]!=pp2[0])
                ans+=pp1[2]-pp1[1]+1;
            p.insert({pp2[0],pp1[1],pp2[2]});
            pp.insert({pp1[1],pp2[2],pp2[0]});
        }
    }
    cout<<ans<<'\n';
}
signed main()
{
	ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout<<fixed<<setprecision(10);
    cin>>tt;
    for(int i=1;i<=tt;i++)
    solve();
}