#include <bits/stdc++.h>
using namespace std;
template <typename... Args>
void logger(string vars, Args&&... values) {
  cout << vars << " = ";
  string delim = "";
  (..., (cout << delim << values, delim = ", "));
}
int32_t main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long tt;
  cin >> tt;
  while (tt--) {
    long long n;
    cin >> n;
    long long a[n], freq[n], b[n];
    map<long long, long long> m;
    for (long long i = 0; i < n; i++) {
      cin >> a[i];
      b[i] = a[i];
      m[a[i]] = 1;
    }
    long long ctr = 0;
    for (auto it : m) {
      m[it.first] = ctr;
      freq[ctr] = 0;
      ctr++;
    }
    vector<long long> v[n];
    for (long long i = 0; i < n; i++) {
      a[i] = m[a[i]];
      freq[a[i]]++;
      v[a[i]].push_back(i);
    }
    long long dp[n];
    long long ans = 0;
    for (long long i = 0; i < n; i++) {
      dp[i] = 1;
      long long ps = -1;
      vector<long long> temp = v[a[i]];
      ps = lower_bound(temp.begin(), temp.end(), i) - temp.begin();
      ps--;
      if (ps != -1) dp[i] = max(dp[i], dp[temp[ps]] + 1);
      if (a[i]) {
        long long pl = -1;
        temp.clear();
        temp = v[a[i] - 1];
        pl = lower_bound(temp.begin(), temp.end(), i) - temp.begin();
        pl--;
        if (pl != -1) {
          long long ans = pl + 1;
          if (freq[a[i] - 1] == pl + 1) ans += dp[temp[0]] - 1;
          dp[i] = max(dp[i], ans + 1);
        }
      }
      ans = max(ans, dp[i]);
    }
    cout << n - ans << "\n";
  }
  return 0;
}
