#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tc=1,tc1=1;
    cin>>tc;
    up:
    while(tc--){
      ll n;
      cin>>n;
      vector<ll>a(n+5);
      for(ll i=1;i<=n;i++){
        cin>>a[i];
      }
      ll c=0,lst=a[1];
      set<array<ll,3>>st;
      for(ll i=1;i<=n;i++){
        if(a[i]==lst){
          c++;
        }
        else {
          st.insert({lst,i-c,i-1});
          c=1,lst=a[i];
        }
      }
      st.insert({lst,n-c+1,n});
      ll ans=0;
      while(1){
        if(st.size()==1){
          break;
        }
        auto v=*st.begin();
        st.erase(v);
        ll val=v[0],sta=v[1],en=v[2],mn=1e18;
        ans+=(v[2]-v[1]+1);
        //cout<<val<<" "<<sta<<" "<<en<<' ';
        if(sta!=1){
          mn=a[sta-1];
        }
        if(en!=n){
          mn=min(mn,a[en+1]);
        }
        a[sta]=mn,a[en]=mn;
        if(a[sta-1]==a[en+1]){
          ll fr=0,ba=n+1;
          for(ll i=sta-2;i>=1;i--){
            if(a[i]!=a[i+1]){
              fr=i;
              break;
            }
          }
          for(ll i=en+2;i<=n;i++){
            if(a[i]!=a[i-1]){
              ba=i;
              break;
            }
          }
          st.erase({mn,fr+1,sta-1});
          st.erase({mn,en+1,ba-1});
          st.insert({mn,fr+1,ba-1});
          //cout<<ans<<"\n";
          continue;
        }
        if(mn==a[sta-1]){
          ll lst=0;
          for(ll i=sta-2;i>=1;i--){
            if(a[i]!=a[i+1]){
              lst=i;
              break;
            }
          }
          st.erase({mn,lst+1,sta-1});
          st.insert({mn,lst+1,en});
        }
        else {
          ll lst=n+1;
          for(ll i=en+2;i<=n;i++){
            if(a[i]!=a[i-1]){
              lst=i;
              break;
            }
          }
          st.erase({mn,en+1,lst-1});
          st.insert({mn,sta,lst-1});
        }
        //cout<<ans<<"\n";
      }
      cout<<ans<<'\n';
    }
}