#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
  long long n;
  cin >> n;
  vector<long long> a(n), b;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
  }
  b = a;
  sort(b.begin(), b.end());
  b.resize(unique(b.begin(), b.end()) - b.begin());
  for (long long i = 0; i < n; i++) {
    a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
  }
  long long ans = 0;
  vector<vector<long long>> pos(n);
  vector<long long> dp(n);
  for (long long i = 0; i < n; i++) {
    pos[a[i]].push_back(i);
  }
  for (long long i = 0; i < n; i++) {
    ans = max(ans, (long long)pos[i].size());
    dp[i] = (long long)pos[i].size();
  }
  for (long long x = n - 2; x >= 0; x--) {
    if (!(long long)pos[x + 1].size() || !(long long)pos[x].size()) continue;
    long long L = pos[x + 1][0], R = pos[x + 1].back();
    long long c = 0;
    for (auto p : pos[x]) {
      c++;
      long long d = lower_bound(pos[x + 1].begin(), pos[x + 1].end(), p) -
                    pos[x + 1].begin();
      if (R < p) break;
      long long cur = c + (long long)pos[x + 1].size() - d;
      if (p <= L) {
        cur = c + dp[x + 1];
      }
      ans = max(ans, cur);
      if (c == (long long)pos[x].size()) dp[x] = max(dp[x], cur);
    }
  }
  cout << n - ans << '\n';
}
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long q;
  cin >> q;
  while (q--) {
    solve();
  }
}
