#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<math.h>
#include<string.h>
#include<deque>
#include<string>
#include<queue>
#include<cstring>
#include<string>
#include<numeric>
#include<bitset>
#include<array>
#include<stack>
using namespace std;
#define lowbit(x) x & ( -x )
#define endl '\n'
#define itn long long
#define int long long
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define ull unsigned long long
#define bug cout<<"bug"<<endl;
//const int p = 131;
const ull  hx = 13331;
int dx[6] = { 0,1,0,-1 };
int dy[6] = { 1,0,-1,0 };
const int N = 10004;
int a[200005];
void tt()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int now = a[1];
    map<int, set<pair<int, int>>>mp;
    set<int>st;
    int l = 1;
    for (int i = 2; i <= n; i++)
    {
        if (a[i] != now)
        {
            st.insert(a[i - 1]);
            mp[a[i - 1]].insert({ l,i - 1 });
            l = i, now = a[i];
        }
    }
    st.insert(a[n]);
    mp[a[n]].insert({ l,n });
    int ans = 0;
    for (auto i : st)
    {
        for (auto t : mp[i])
        {
            int l = t.first, r = t.second;
            if (l == 1)
            {
                if (r == n)
                {
                    cout << ans << endl;
                    return;
                }
                int cnt = a[r + 1];
                auto tt = mp[cnt].lower_bound({ r + 1,r + 1 });
                ans += r - l + 1;
                a[l] = a[r + 1];
                mp[cnt].insert({ l,(*tt).second });
                mp[cnt].erase(tt);
                continue;
            }
            if (r == n)
            {
                if (l == 1)
                {
                    cout << ans << endl;
                    return;
                }
                int cnt = a[l - 1];
                auto tt = prev(mp[cnt].lower_bound({ l,l }));
                ans += r - l + 1;
                mp[cnt].insert({ (*tt).first, r });
                mp[cnt].erase(tt);
                continue;
            }
            int cnt1 = a[l - 1], cnt2 = a[r + 1];
            ans += r - l + 1;
            if (cnt1 < cnt2)
            {
                int cnt = cnt1;
                auto tt = prev(mp[cnt].lower_bound({ l,l }));
                ans += r - l + 1;
                mp[cnt].insert({ (*tt).first, r });
                mp[cnt].erase(tt);
            }
            else
            {
                int cnt = a[r] + 1;
                auto tt = mp[cnt].lower_bound({ r + 1,r + 1 });
                ans += r - l + 1;
                a[l] = a[r + 1];
                mp[cnt].insert({ l,(*tt).second });
                mp[cnt].erase(tt);

            }
        }
    }
    cout << ans << endl;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        tt();
    }
}