#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  int t;
  cin >> t;
  for (ll _ = 0, _Len = (t); _ < _Len; ++_) {
    ll n;
    cin >> n;
    vector<ll> a(n);
    vector<pair<ll, ll>> sorted;
    for (ll i = 0, iLen = (n); i < iLen; ++i) {
      cin >> a[i];
      sorted.emplace_back(a[i], i);
    }
    sort(sorted.begin(), sorted.end());
    int comp_n = -1, prev_n = -1;
    vector<int> num_cnt;
    for (auto &[num, index] : sorted) {
      if (prev_n < num) {
        prev_n = num;
        comp_n++;
        num_cnt.emplace_back(0);
      }
      a[index] = comp_n;
      num_cnt.back()++;
    }
    map<int, int> mp;
    vector<int> current_cnt(num_cnt.size());
    vector<vector<int>> dp(n + 1, vector<int>(3, 1));
    int ans = 0;
    for (ll i = 0, iLen = (n); i < iLen; ++i) {
      current_cnt[a[i]]++;
      auto itr1 = mp.find(a[i]), itr2 = mp.find(a[i] - 1);
      if (itr1 != mp.end()) {
        int j = itr1->second;
        dp[i][0] = dp[j][0] + 1;
        dp[i][1] = dp[j][1] + 1;
        dp[i][2] = dp[j][2] + 1;
      }
      if (itr2 != mp.end()) {
        int j = itr2->second;
        dp[i][2] = max(dp[i][2], dp[j][0] + 1);
        if (current_cnt[a[i]] == 1) {
          dp[i][1] = max(dp[i][1], dp[j][0] + 1);
        }
        if (num_cnt[a[i] - 1] == current_cnt[a[i] - 1]) {
          dp[i][2] = max(dp[i][2], dp[j][1] + 1);
        }
        if (itr1 == mp.end() && num_cnt[a[i] - 1] == current_cnt[a[i] - 1]) {
          dp[i][1] = max(dp[i][1], dp[j][1] + 1);
        }
      }
      ans = max({ans, dp[i][0], dp[i][1], dp[i][2]});
      mp[a[i]] = i;
    }
    cout << n - ans << "\n";
  }
  return 0;
}
