#include <bits/stdc++.h>
using namespace std;
int t;
int n;
int a[200005];
int dp[200005][2];
int cnt[200005];
int us[200005];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cerr.tie(0);
  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      dp[i][0] = dp[i][1] = 0;
      cnt[i] = 0;
      us[i] = 0;
    }
    vector<int> v;
    for (int i = 0; i < n; i++) v.push_back(a[i]);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 0; i < n; i++) {
      a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
      cnt[a[i]]++;
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
      if (dp[a[i]][0] == 0) {
        if (a[i] > 0) dp[a[i]][0] += max(us[a[i] - 1], dp[a[i] - 1][1]);
      }
      dp[a[i]][0]++;
      us[a[i]]++;
      cnt[a[i]]--;
      if (cnt[a[i]] == 0) dp[a[i]][1] = dp[a[i]][0];
      res = max(res, dp[a[i]][0]);
      if (a[i] > 0) {
        res = max(res, us[a[i] - 1] + cnt[a[i]] + 1);
        res = max(res, dp[a[i] - 1][1] + cnt[a[i]] + 1);
      }
    }
    cout << n - res << "\n";
  }
  return 0;
}
