#include <bits/stdc++.h>
#define ll long long
#define int long long
#define INF 0x3f3f3f3f
#define llINF 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(), x.end()
#define alll(x, t) x.begin() + t, x.end()
#define rall(x) x.rbegin(), x.rend()
#define ull unsigned long long
#define PII pair<int, int>
#define fi first
#define se second
#define pb push_back
#define lowbit(x) ((x) & (-x))
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int lcm(int a, int b) { return (a / gcd(a, b)) * b; }
const int mod = 1e9 + 7;
inline ll qpow(ll n, ll m) // 有的时候用的时候记住删掉mod,long long最多为2^63,约等于9e18
{
    ll res = 1;
    while (m)
    {
        if (m & 1)
            res = res * n % mod;
        n = n * n % mod;
        m >>= 1;
    }
    return res;
}
inline bool isp(int x)
{
    if (x == 1)
        return false;
    if (x <= 3)
        return true;
    for (int i = 2; i <= x / i; i++)
    {
        if (x % i == 0)
            return false;
    }
    return true;
}
// cout << fixed << setprecision(3) << s;
inline void kfk_dm()
{
    // 记得看数据范围
    int n;
    cin >> n;
    int cnt = 1;
    int id = 0;
    vector<pair<int, array<int, 3>>> c;
    vector<int> a(n + 1);
    int mx = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        mx = max(mx, a[i]);
        if (i == 1)
            continue;
        if (a[i] == a[i - 1])
            cnt++;
        else
        {
            c.push_back({a[i - 1], {id, id++, cnt}});
            cnt = 1;
        }
    }
    c.push_back({a[n], {id, id, cnt}});
    vector<int> vis(id);
    priority_queue<pair<int, array<int, 3>>, vector<pair<int, array<int, 3>>>, greater<pair<int, array<int, 3>>>> q;
    for (int i = 0; i <= id; i++)
        q.push(c[i]);
    int ans = 0;
    while (q.top().first < mx)
    {
        auto h = q.top();
        q.pop();
        int l = h.second[0] - 1, r = h.second[1] + 1;
        int x = INF;
        if (l >= 0 && r <= id)
        {
            int lnum = c[l].first;
            int rnum = c[r].first;
            if (lnum < rnum)
            {
                if (lnum > h.first)
                {
                    h.second[0]--;
                    x = lnum;
                    c[l + 1].first = x;
                }
                else 
                {
                    h.second[1]++;
                    x = rnum;
                    c[r - 1].first = x;
                }
            }
            else
            {
                if (rnum > h.first)
                {
                    h.second[1]++;
                    x = rnum;
                    c[r - 1].first = x;
                }
                else 
                {
                    h.second[0]--;
                    x = lnum;
                    c[l + 1].first = x;
                }
            }
        }
        else if (l >= 0)
        {
            h.second[0]--;
            x = c[l].first;
            c[l + 1].first = x;
        }
        else
        {
            h.second[1]++;
            x = c[r].first;
            c[r - 1].first = x;
        }
        h.first = x;
        ans += h.second[2];
        q.push(h);
    }
    cout << ans << "\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        kfk_dm();
    return 0;
}