#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < (N); i++) cin >> A[i];
    map<int, vector<int> > Pm;
    for (int i = 0; i < (N); i++) {
      Pm[A[i]].push_back(i);
    }
    vector<vector<int> > P;
    for (auto& a : Pm) P.push_back(a.second);
    int cur = 0;
    int ans = 0;
    while (cur < (int)(P).size()) {
      int cnt = (int)(P[cur]).size();
      if (cur > 0) {
        for (int i = 0; i < ((int)(P[cur - 1]).size()); i++) {
          if (P[cur - 1][i] < P[cur][0]) {
            cnt++;
          }
        }
      }
      cur++;
      while (cur < (int)(P).size() &&
             P[cur - 1][(int)(P[cur - 1]).size() - 1] < P[cur][0]) {
        cnt += (int)(P[cur]).size();
        cur++;
      }
      if (cur < (int)(P).size()) {
        for (int i = 0; i < ((int)(P[cur]).size()); i++) {
          if (P[cur][i] > P[cur - 1][(int)(P[cur - 1]).size() - 1]) cnt++;
        }
      }
      ans = max(ans, cnt);
    }
    for (int i = 0; i < ((int)(P).size() - 1); i++) {
      vector<pair<int, bool> > E;
      for (int j = 0; j < ((int)(P[i]).size()); j++) {
        E.push_back({P[i][j], true});
      }
      for (int j = 0; j < ((int)(P[i + 1]).size()); j++) {
        E.push_back({P[i + 1][j], false});
      }
      int cnt = (int)(P[i + 1]).size();
      ans = max(ans, cnt);
      sort(E.begin(), E.end());
      for (int j = 0; j < ((int)(E).size()); j++) {
        if (E[j].second) {
          cnt++;
          ans = max(ans, cnt);
        } else {
          cnt--;
        }
      }
    }
    cout << N - ans << nl;
  }
  return 0;
}
