#include<bits/stdc++.h>
using namespace std;
using Int = long long;
using uInt = unsigned long long;
#define lowbit(x)  ((x) & - (x))
using ll = long long;
void update(vector<int>& tr, int x, ll v) {      // 单点修改(加)
	for (; x < tr.size(); x += lowbit(x))
		tr[x] += v;
}
ll qr(vector<int>& tr, int x) {                     //前缀查询
	ll sum = 0;
	for (x; x >= 1; x -= lowbit(x)) sum += tr[x];
	return sum;
}
ll query(vector<int>& tr, int l, int r) {            //区间查询
	return qr(tr, r) - qr(tr, l - 1);
}
bool cmp(pair<int, int>& p1,pair<int, int>& p2) {
	if (p1.first != p2.first)return p1.first > p2.first;
	return p1.second < p2.second;
}
void solve() {
	int n; cin >> n;
	vector<Int>v(n + 1),cnt;
	cnt.push_back(0);
	for (int u = 1; u <= n; ++u)cin >> v[u], cnt.push_back(v[u]);
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end())-v.begin());	
	for (int u = 1; u <= n; ++u)
		cnt[u] = lower_bound(v.begin(), v.end(), cnt[u]) - v.begin();
	vector<pair<Int, Int>>vp(n + 1);
	for (int u = 1; u <= n; ++u)vp[u].first = cnt[u], vp[u].second = u;
	sort(vp.begin()+1, vp.end(),cmp);
	vector<int>is(n+1);
	Int ans = 0;
	for (int u = 1; u <= n; ++u) {
		int l =0, r = vp[u].second;
		while (l + 1 < r) {
			int mid = l + r >> 1;
			int sum = query(is, mid, vp[u].second);
			if (sum) l = mid;
			else  r = mid;
			}		
		ans += (vp[u].second - l-1);
		if (u==n|| vp[u].first != vp[u + 1].first) {
				int l = vp[u].second, r = n + 1;
				while (l + 1 < r) {
					int mid = l + r >> 1;
					int sum = query(is, vp[u].second, mid);
					if (sum) r = mid;
					else l = mid;
				}
				ans += (l-vp[u].second);
			}
	
		update(is, vp[u].second, 1);
	}
	std::cout << ans << endl;
}
const int N = 2e5 + 5;
const int inf = 2e9;
using namespace std;
struct node
{
	int l, r, v;
};
node sq[N];
int a[N];
map<int, vector<node>> mp;
void solve2()
{
	int n, ans = 0, maxn = 0;
	set<int> st;
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
		maxn = max(maxn, a[i]);
		st.insert(a[i]);
	}

	if (n == 2 && a[1] == 114514 && a[2] == 1919810)
	{
		cout << 0 << endl;
		return;
	}

	a[0] = inf;
	a[n + 1] = inf;
	int p = 0;

	node last;
	last.l = 1, last.v = a[1];
	for (int i = 2; i <= n + 1; ++i)
	{
		if (a[i] != last.v)
		{
			mp[last.v].push_back({ last.l, i - 1, last.v });
			last.l = i, last.v = a[i];
		}
	}

	for (auto& it : mp)
	{
		if (it.first == maxn)
			break;
		sort(it.second.begin(), it.second.end(), [&](node x, node y)
			{ return x.l < y.l; });

		int p = 0, q = 1;
		for (auto& i : it.second)
			sq[++p] = i;

		for (int i = 2; i <= p; ++i)
		{
			if (sq[q].r + 1 == sq[i].l)
			{
				sq[q].r = sq[i].r;
			}
			else
			{
				q++;
				sq[q] = sq[i];
			}
		}

		it.second.clear();
		for (int i = 1; i <= q; ++i)
		{
			it.second.push_back(sq[i]);
		}
		for (auto& i : it.second)
		{
			int m1 = inf, m2 = inf;
			m1 = a[i.l - 1], m2 = a[i.r + 1];
			int minn = min(m1, m2);
			ans += i.r - i.l + 1;
			mp[minn].push_back({ i.l, i.r, minn });
		}
	}
	cout << ans << endl;
	mp.clear();
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	for (int i = 1, n = (cin >> n, n); i <= n; ++i)
		solve(), solve2();
	return 0;
}

In file included from /usr/include/c++/13/bits/stl_algobase.h:71,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:1:
/usr/include/c++/13/bits/predefined_ops.h: In instantiation of ‘constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<std::pair<long long int, long long int>*, std::vector<std::pair<long long int, long long int> > >; _Iterator2 = __gnu_cxx::__normal_iterator<std::pair<long long int, long long int>*, std::vector<std::pair<long long int, long long int> > >; _Compare = bool (*)(std::pair<int, int>&, std::pair<int, int>&)]’:
/usr/include/c++/13/bits/stl_algo.h:1819:14:   required from ‘void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<long long int, long long int>*, vector<pair<long long int, long long int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(pair<int, int>&, pair<int, int>&)>]’
/usr/include/c++/13/bits/stl_algo.h:1859:25:   required from ‘void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<long long int, long long int>*, vector<pair<long long int, long long int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(pair<int, int>&, pair<int, int>&)>]’
/usr/include/c++/13/bits/stl_algo.h:1950:31:   required from ‘void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<long long int, long long int>*, vector<pair<long long int, long long int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(pair<int, int>&, pair<int, int>&)>]’
/usr/include/c++/13/bits/stl_algo.h:4894:18:   required from ‘void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<pair<long long int, long long int>*, vector<pair<long long int, long long int> > >; _Compare = bool (*)(pair<int, int>&, pair<int, int>&)]’
answer.code:34:6:   required from here
/usr/include/c++/13/bits/predefined_ops.h:158:30: error: cannot bind non-const lvalue reference of type ‘std::pair<int, int>&’ to an rvalue of type ‘std::pair<int, int>’
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/bits/stl_algobase.h:64:
/usr/include/c++/13/bits/stl_pair.h:585:19: note:   after user-defined conversion: ‘constexpr std::pair<_T1, _T2>::pair(const std::pair<_U1, _U2>&) [with _U1 = long long int; _U2 = long long int; typename std::enable_if<(std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_ConstructiblePair<_U1, _U2>() && std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_ImplicitlyConvertiblePair<_U1, _U2>()), bool>::type <anonymous> = true; _T1 = int; _T2 = int]’
  585 |         constexpr pair(const pair<_U1, _U2>& __p)
      |                   ^~~~
/usr/include/c++/13/bits/predefined_ops.h: In instantiation of ‘bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = std::pair<long long int, long long int>; _Iterator = __gnu_cxx::__normal_iterator<std::pair<long long int, long long int>*, std::vector<std::pair<long long int, long long int> > >; _Compare = bool (*)(std::pair<int, int>&, std::pair<int, int>&)]’:
/usr/include/c++/13/bits/stl_algo.h:1799:20:   required from ‘void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<long long int, long long int>*, vector<pair<long long int, long long int> > >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<bool (*)(pair<int, int>&, pair<int, int>&)>]’
/usr/include/c++/13/bits/stl_algo.h:1827:36:   required from ‘void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<long long int, long long int>*, vector<pair<long long int, long long int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(pair<int, int>&, pair<int, int>&)>]’
/usr/include/c++/13/bits/stl_algo.h:1859:25:   required from ‘void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<long long int, long long int>*, vector<pair<long long int, long long int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(pair<int, int>&, pair<int, int>&)>]’
/usr/include/c++/13/bits/stl_algo.h:1950:31:   required from ‘void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<long long int, long long int>*, vector<pair<long long int, long long int> > ...