#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
const int N = 2e5 + 10;
const long long mod = 1e9 + 7;
const long long mod2 = 998244353;
const long long inf = 8e18;
const int LOG = 22;
long long pw(long long a, long long b, long long M) {
  return (!b ? 1
             : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M
                      : pw(a * a % M, b / 2, M)));
}
int v[N], dp[N], cnt[N], cu[N], Fi[N], kol[N], L[N], A[N];
void solve() {
  map<int, int> mp;
  int n;
  cin >> n;
  A[0] = -1;
  for (int i = 0; i <= n + 1; i++) {
    if (i && i <= n) {
      cin >> v[i];
      A[i] = v[i];
    }
    dp[i] = cnt[i] = cu[i] = Fi[i] = L[i] = kol[i] = 0;
  }
  sort(A + 1, A + n + 1);
  int ptr = 0;
  for (int i = 1; i <= n; i++) {
    if (A[i] != A[i - 1]) {
      ptr++;
    }
    mp[A[i]] = ptr;
  }
  for (int i = n; ~(i - 1); i--) {
    v[i] = mp[v[i]];
    Fi[v[i]] = i;
    cnt[v[i]]++;
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    dp[i] = max(dp[L[v[i]]], cu[v[i] - 1]) + 1;
    if (cnt[v[i] - 1] == cu[v[i] - 1]) {
      dp[i] = max(dp[i], kol[v[i] - 1] + 1);
    }
    ans = max(ans, dp[i]);
    L[v[i]] = i;
    ++cu[v[i]];
    if (cu[v[i]] == cnt[v[i]]) {
      kol[v[i]] = dp[Fi[v[i]]] + cnt[v[i]] - 1;
    }
  }
  cout << n - ans << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  int q;
  cin >> q;
  while (q--) {
    solve();
  }
  return 0;
}
