#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct r {
    long long v, c;
    bool operator<(const r& o) const {
        return v < o.v;
    }
};

int main() {
    int t;
    cin >> t;
    while (t-- > 0) {
        solve();
    }
    return 0;
}

void solve() {
    int n;
    cin >> n;
    long long cnt = 0, val = 0;
    priority_queue<r, vector<r>, greater<r>> pq;
    queue<r> arr;

    for (int i = 0; i < n; i++) {
        long long key;
        cin >> key;
        if (val != key) {
            if (cnt != 0) arr.push({ val, cnt });
            val = key;
            cnt = 1;
        }
        else cnt++;
    }
    arr.push({ val, cnt });
    long long sum = 0;
    int t = arr.size();
    for (int i = 0; i < t; i++) {
        r key = arr.front();
        arr.pop();
        pq.push(key);
        while (!pq.empty() && pq.top().v <= key.v) {
            if (pq.size() < 2) break;
            r pop = pq.top();
            pq.pop();
            r update = pq.top();
            pq.pop();
            update.c += pop.c;
            pq.push(update);
            sum += pop.c;
        }
    }

    while (pq.size() > 1) {
        r pop = pq.top();
        pq.pop();
        r update = pq.top();
        pq.pop();
        update.c += pop.c;
        pq.push(update);
        sum += pop.c;
    }

    cout << sum << endl;
}

answer.code: In function ‘int main()’:
answer.code:18:9: error: ‘solve’ was not declared in this scope
   18 |         solve();
      |         ^~~~~
In file included from /usr/include/c++/13/string:49,
                 from /usr/include/c++/13/bits/locale_classes.h:40,
                 from /usr/include/c++/13/bits/ios_base.h:41,
                 from /usr/include/c++/13/ios:44,
                 from /usr/include/c++/13/ostream:40,
                 from /usr/include/c++/13/iostream:41,
                 from answer.code:1:
/usr/include/c++/13/bits/stl_function.h: In instantiation of ‘constexpr bool std::greater<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = r]’:
/usr/include/c++/13/bits/predefined_ops.h:196:23:   required from ‘bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<r*, std::vector<r> >; _Value = r; _Compare = std::greater<r>]’
/usr/include/c++/13/bits/stl_heap.h:140:48:   required from ‘void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<r*, vector<r> >; _Distance = long int; _Tp = r; _Compare = __gnu_cxx::__ops::_Iter_comp_val<greater<r> >]’
/usr/include/c++/13/bits/stl_heap.h:216:23:   required from ‘void std::push_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<r*, vector<r> >; _Compare = greater<r>]’
/usr/include/c++/13/bits/stl_queue.h:741:16:   required from ‘void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = r; _Sequence = std::vector<r>; _Compare = std::greater<r>; value_type = r]’
answer.code:46:16:   required from here
/usr/include/c++/13/bits/stl_function.h:398:20: error: no match for ‘operator>’ (operand types are ‘const r’ and ‘const r’)
  398 |       { return __x > __y; }
      |                ~~~~^~~~~
In file included from /usr/include/c++/13/string:48:
/usr/include/c++/13/bits/stl_iterator.h:469:5: note: candidate: ‘template<class _Iterator> constexpr bool std::operator>(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)’
  469 |     operator>(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:469:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_function.h:398:20: note:   ‘const r’ is not derived from ‘const std::reverse_iterator<_Iterator>’
  398 |       { return __x > __y; }
      |                ~~~~^~~~~
/usr/include/c++/13/bits/stl_iterator.h:514:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> constexpr bool std::operator>(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)’
  514 |     operator>(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:514:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_function.h:398:20: note:   ‘const r’ is not derived from ‘const std::reverse_iterator<_Iterator>’
  398 |       { return __x > __y; }
      |                ~~~~^~~~~
/usr/include/c++/13/bits/stl_iterator.h:1725:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> constexpr bool std::operator>(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)’
 1725 |     operator>(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1725:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_function.h:398:20: note:   ‘const r’ is not derived from ‘const std::move_iterator<_IteratorL>’
  398 |       { return __x > __y; }
      |                ~~~~^~~~~
/usr/include/c++/13/bits/stl_iterator.h:1784:5: note: candidate: ‘template<class _Iterator> constexpr bool std::operator>(const move_iterator<_IteratorL>&, const move_iterator<_IteratorL>&)’
 1784 |     operator>(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1784:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_function.h:398:20: note:   ‘const r’ is not derived from ‘const std::move_iterator<_IteratorL>’
  398 |       { return __x > __y; }
      |                ~~~~^~~~~