#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
int t, n;
int a[1000010], b[1000010], r[1000010];
int dp[1000010];
map<int, int> ma;
map<int, int> cnt;
int main() {
  ios_base::sync_with_stdio(false);
  cin >> t;
  while (t--) {
    ma.clear();
    cnt.clear();
    cin >> n;
    for (int i = 1; i <= n; ++i) {
      cin >> a[i];
      b[i] = a[i];
      dp[i] = 1;
      r[i] = 0;
    }
    sort(b + 1, b + 1 + n);
    for (int i = 1; i <= n; ++i) {
      ma[b[i]]++;
    }
    int len = unique(b + 1, b + 1 + n) - b - 1;
    int maxx = 0;
    for (int i = 1; i <= n; ++i) {
      int pos = lower_bound(b + 1, b + 1 + len, a[i]) - b;
      if (cnt[a[i]] == 0) {
        if (cnt[b[pos - 1]] == ma[b[pos - 1]])
          dp[i] = dp[r[pos - 1]] + 1;
        else
          dp[i] = cnt[b[pos - 1]] + 1;
      } else {
        dp[i] = dp[r[pos]] + 1;
        if (cnt[b[pos - 1]] == ma[b[pos - 1]]) {
          maxx = max(maxx, dp[r[pos - 1]] + ma[a[i]] - cnt[a[i]]);
        }
      }
      r[pos] = i;
      cnt[a[i]]++;
    }
    for (int i = 1; i <= n; ++i) {
      maxx = max(maxx, dp[i]);
    }
    cout << n - maxx << "\n";
  }
  return 0;
}
