#include <bits/stdc++.h>
using namespace std;
void solve() {
  int n, ans = 0;
  cin >> n;
  vector<int> a(n), b(n), dp(n);
  vector<vector<int>> pos(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    b[i] = a[i];
  }
  sort(b.begin(), b.end());
  b.resize(unique(b.begin(), b.end()) - b.begin());
  for (int i = 0; i < n; ++i) {
    a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
    pos[a[i]].push_back(i);
  }
  for (int i = 0; i < n; ++i) {
    if (pos[i].empty()) continue;
    dp[i] = pos[i].size();
    if (i > 0 && !pos[i - 1].empty() && pos[i - 1].back() < pos[i][0])
      dp[i] = max(dp[i], dp[i - 1] + (int)pos[i].size());
    ans = max(ans, dp[i]);
    if (i > 0) {
      int less = 0, bigger = 0;
      for (int v : pos[i - 1])
        if (v < pos[i][0]) less++;
      dp[i] = max(dp[i], less + (int)pos[i].size());
      ans = max(ans, dp[i]);
      for (int v : pos[i])
        if (!pos[i - 1].empty() && v > pos[i - 1].back()) bigger++;
      ans = max(ans, dp[i - 1] + bigger);
      vector<pair<int, int>> ord;
      for (int v : pos[i]) ord.emplace_back(v, 1);
      for (int v : pos[i - 1]) ord.emplace_back(v, 0);
      sort(ord.begin(), ord.end());
      less = bigger = 0;
      for (auto v : ord) {
        if (v.second)
          bigger++;
        else {
          less++;
          bigger = max(bigger, less);
        }
      }
      ans = max(ans, bigger);
    }
  }
  cout << n - ans << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) solve();
}
