#include <bits/stdc++.h>
using namespace std;
vector<int> compress(vector<int> a) {
  set<int> s;
  map<int, int> S;
  for (int& x : a) s.insert(x);
  int cnt = 0;
  for (int x : s) {
    S[x] = ++cnt;
  }
  for (int& x : a) x = S[x];
  return a;
}
void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int& x : a) cin >> x;
  a = compress(a);
  int mxa = 0;
  for (int& x : a) mxa = max(mxa, x);
  vector<int> mn(mxa + 1, 1e9), mx(mxa + 1);
  for (int i = 0; i < n; i++) {
    mn[a[i]] = min(mn[a[i]], i);
    mx[a[i]] = max(mx[a[i]], i);
  }
  vector<int> occ(mxa + 1), dp(mxa + 1);
  vector<vector<int>> in(mxa + 1);
  for (int i = 0; i < n; i++) in[a[i]].push_back(i);
  for (int& x : a) ++occ[x];
  int ans = 0;
  for (int& x : a) ans = max(ans, occ[x]);
  for (int i = mxa; i > 0; i--) {
    if (i == mxa) {
      dp[i] = occ[i];
    } else {
      dp[i] = occ[i];
      if (mx[i] < mn[i + 1]) {
        dp[i] += dp[i + 1];
      } else {
        auto it = lower_bound(in[i + 1].begin(), in[i + 1].end(), mx[i]);
        int many = (int)(in[i + 1].end() - it);
        dp[i] += many;
      }
    }
  }
  for (int& x : dp) ans = max(ans, x);
  for (int i = mxa - 1; i > 0; i--) {
    int cur = 0, res = 0;
    for (int& x : in[i]) {
      ++cur;
      auto it = lower_bound(in[i + 1].begin(), in[i + 1].end(), x);
      res = max(res, cur + (int)(in[i + 1].end() - it));
    }
    ans = max(ans, res);
  }
  for (int i = 2; i <= mxa; i++) {
    int addition = 0;
    auto it = upper_bound(in[i - 1].begin(), in[i - 1].end(), mn[i]);
    addition = it - in[i - 1].begin();
    ans = max(ans, dp[i] + addition);
  }
  cout << n - ans;
  return;
}
int main() {
  int n;
  cin >> n;
  while (n--) {
    solve();
    cout << endl;
  }
  return 0;
}
