#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> comp;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      comp.push_back(a[i]);
    }
    sort(comp.begin(), comp.end());
    comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
    int sz = comp.size();
    unordered_map<int, int> M;
    for (int i = 0; i < sz; i++) {
      M[comp[i]] = i;
    }
    for (int i = 0; i < n; i++) a[i] = M[a[i]];
    vector<int> U[sz + 1];
    for (int i = 0; i < n; i++) {
      U[a[i]].push_back(i);
    }
    int b[sz + 1];
    fill(b, b + 1 + sz, 0);
    int ans = 0;
    for (int i = sz - 1; ~i; i--) {
      b[i] = U[i].size();
      if (U[i + 1].size() && U[i + 1][0] >= U[i].back())
        b[i] += b[i + 1];
      else if (U[i + 1].size() && U[i + 1].back() >= U[i].back()) {
        b[i] += U[i + 1].end() -
                lower_bound(U[i + 1].begin(), U[i + 1].end(), U[i].back());
      }
      ans = max(ans, b[i]);
      for (int j = 0; j < U[i].size(); j++) {
        if (U[i + 1].size()) {
          if (U[i + 1][0] >= U[i][j]) {
            ans = max(ans, j + 1 + b[i + 1]);
          } else if (U[i + 1].back() >= U[i][j]) {
            ans = max(ans, j + 1 +
                               (int)(U[i + 1].end() -
                                     lower_bound(U[i + 1].begin(),
                                                 U[i + 1].end(), U[i][j])));
          }
        }
      }
    }
    cout << n - ans << '\n';
  }
}
