#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
	int first,second,value;
	bool operator<(const node&t2)const
	{
		if(first==t2.first)
		{
			return second>t2.second;
		}
		else
		{
			return first>t2.first;
		}
	} 
};

int b[200000 + 10];
void solve(){
	priority_queue<struct node> qq,t;
	vector<struct node> a;
	int N;
	cin >> N;
	int maxn=0;//最大值 
	for(int i=0;i<N;i++)
	{
		std::cin >> b[i];
		maxn=max(maxn,b[i]);
	}
	b[N + 1] = INT_MAX;
	struct node now={b[0], 0ll, 1ll};
	for(int i=1;i<N;i++)
	{
		if (b[i] == now.first) {
			now.value++;
		} else {
			qq.push (now);
			now = {b[i], i, 1};
		}
	 }
	qq.push (now);
	//qq中的东西输出 
//	t=qq;
//	while(!t.empty())
//	{
//		struct node tt=t.top();
//		cout<< tt.first<<" "<< tt.second<<" "<< tt.value<<"\n";
//		t.pop();
//	}
//	return ;
	int result = 0;
	int nn = 1;
	while (qq.size () != 1) {
		nn++;
//		if (nn == 10) {
//			break;
//		} 
		struct node now = qq.top ();
		qq.pop ();
//		std::cout << now.first << " " << now.second << " " << now.value << "\n";
		if (now.first == qq.top().first && now.second + now.value == qq.top().second) {
			now.value = now.value + qq.top().value;
			qq.pop ();
			qq.push (now);
			continue;
		}
		if (now.second == 0) {
			now.first = b[now.second + now.value];
			result = result + now.value; 
		} else if (now.second == N - 1) {
			now.first = b[now.second - 1];
			result = result + now.value;
		} else {
			int now_left = b[now.second - 1];
			int now_right = b[now.second + now.value];
			if (now_left == 0) {
				now_left = INT_MAX;
			}
			if (now_right == 0) {
				now_right = INT_MAX; 
			} 
//			std::cout << now_left << " " << now_right << "\n";
			if (now_left <= now_right) {
				now.first = b[now.second - 1];
			} else {
				now.first = b[now.second + now.value];
			}
			result = result + now.value;
		}
		qq.push(now);
	}
	std::cout << result << "\n";
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--)
	  solve();
	return 0;
}
/*
1
9
2 2 2 1 3 2 2 1 1  
*/