#include <iostream>
#include <cstring>
using namespace std;
#define ll long long 
const int N = 3e5+10;
#include <cstring>
ll a[N];
ll tree[N<<2];
ll tag[N<<2];
ll Same[N<<2];
ll ls(ll p){return p<<1;}
ll rs(ll p){return p<<1|1;}
inline void build(ll p,ll pl,ll pr){
    tag[p] = 0;
    Same[p] = 0;
    if(pl==pr) {tree[p]=a[pl];Same[p]=1;return;}
    ll mid = (pl+pr) >> 1;
    build(ls(p),pl,mid);
    build(rs(p),mid+1,pr);
    tree[p] = min(tree[ls(p)],tree[rs(p)]);
    if(tree[ls(p)]==tree[rs(p)]&&Same[ls(p)]==1&&Same[rs(p)]==1){
        Same[p] = 1;
    }
}

inline void update(ll L,ll R,ll p,ll pl,ll pr,ll d){
    if(L<=pl&&pr<=R){
        tag[p] = d;
        tree[p] = d;
        return;
    }
    if(tag[p]){
        ll mid = (pl+pr) >> 1;
        tag[ls(p)] = tag[p];
        tree[ls(p)] = tag[p];
        tag[rs(p)] = tag[p];
        tree[rs(p)] = tag[p];
        tag[p] = 0;
    }
    ll mid = (pl+pr) >> 1;
    if(L<=mid) update(L,R,ls(p),pl,mid,d);
    if(R>mid) update(L,R,rs(p),mid+1,pr,d);
    tree[p] = min(tree[ls(p)],tree[rs(p)]);
    if(tree[ls(p)]==tree[rs(p)]&&Same[ls(p)]==1&&Same[rs(p)]==1){
        Same[p] = 1;
    }
}
inline ll query(ll p,ll pl,ll pr){
    //先找到两个字段谁是最小
    if(pl==pr) return pl;//返回这个位置
    if(tag[p]){
        ll mid = (pl+pr) >> 1;
        tag[ls(p)] = tag[p];
        tree[ls(p)] = tag[p];
        tag[rs(p)] = tag[p];
        tree[rs(p)] = tag[p];
        tag[p] = 0;
    }
    ll mid = (pl+pr) >> 1;
    if(tree[ls(p)]<=tree[rs(p)]){
        return query(ls(p),pl,mid);
    }else{
        return query(rs(p),mid+1,pr);
    }
}
inline ll query2(ll p,ll pl,ll pr){
    ll mid = (pl+pr) >> 1;
    if(pl==pr){
        return pl;
    }
    if(tag[p]){
        ll mid = (pl+pr) >> 1;
        tag[ls(p)] = tag[p];
        tree[ls(p)] = tag[p];
        tag[rs(p)] = tag[p];
        tree[rs(p)] = tag[p];
        tag[p] = 0;
    }
    if(tree[ls(p)]<tree[rs(p)]){//那就从左边开始找
        if(Same[ls(p)]==1){
            return mid;
        }
        return query2(ls(p),pl,mid);
    }else if(tree[ls(p)]>tree[rs(p)]){
        if(Same[rs(p)]==1){
            return pr;
        }
        return query2(rs(p),mid+1,pr);
    }else if(tree[ls(p)]==tree[rs(p)]){
        //那就从两个中都找一遍
        //如果左边都是一样的，就看右边，如果左边不一样就看左边
        if(Same[p]==1){
            return pr;
        }
        if(Same[ls(p)]==1&&Same[rs(p)]==0){

        }
        if(Same[ls(p)]==1){//如果都相同，就看右边，如果不相同再看左边
            return query2(rs(p),mid+1,pr);
        }else{
            return query2(ls(p),pl,mid);
        }
    }
}
inline ll qMin(ll p,ll pl,ll pr,ll pos){
    while(pl!=pr){
        if(tag[p]){
            ll mid = (pl+pr) >> 1;
            tag[ls(p)] = tag[p];
            tree[ls(p)] = tag[p];
            tag[rs(p)] = tag[p];
            tree[rs(p)] = tag[p];
            tag[p] = 0;
        }
        ll mid = (pl+pr) >> 1;
        if(pos>=pl&&pos<=mid){
            p = ls(p);
            pr =  mid;
        }else{
            p = rs(p);
            pl = mid+1;
        }
    }
    return tree[p];
}
int main()
{
    int t;scanf("%d",&t);
    while(t--){
        memset(tag,0,sizeof(tag));
        int n;scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        build(1,1,n);
        ll Ans = 0;
        while(1){
            //找到最小值，和它的左右
            ll left = query(1,1,n);
            ll right = query2(1,1,n);
            //找到左右的旁边两个中的最小值
            if(left==1&&right==n) break;
            if(left==1){
                //取pl == right+1的数据
                ll Min = qMin(1,1,n,right+1);
                update(left,right,1,1,n,Min);
                Ans += (right - left + 1);
                continue;
            }
            if(right==n){
                ll Min = qMin(1,1,n,left-1);
                update(left,right,1,1,n,Min);
                Ans += (right - left + 1);
                continue;
            }
            ll Min = min(qMin(1,1,n,left-1),qMin(1,1,n,right+1));
            update(left,right,1,1,n,Min);
            Ans += (right - left + 1);
        }
        cout << Ans << endl;
    }
    return 0;
}