#include <bits/stdc++.h>
using namespace std;
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long int t;
  cin >> t;
  while (t--) {
    long long int n;
    cin >> n;
    long long int a[n + 1];
    map<long long int, long long int> m;
    long long int ar[n + 1];
    vector<long long int> v;
    long long int c = 1;
    a[0] = -1;
    for (long long int i = 1; i < (n + 1); i++) {
      cin >> a[i];
      ar[i] = a[i];
    }
    sort(a + 1, a + n + 1);
    for (long long int i = 1; i < (n + 1); i++) {
      if (a[i] != a[i - 1]) {
        m[a[i]] = c;
        c++;
      }
    }
    map<long long int, long long int> cnt;
    long long int dp[n + 1][3];
    cnt[0] = 0;
    dp[0][0] = 0;
    dp[0][1] = 0;
    dp[0][2] = 0;
    for (long long int i = 1; i < (n + 1); i++) {
      ar[i] = m[ar[i]];
      cnt[ar[i]]++;
      dp[ar[i]][0] = 0;
      dp[ar[i]][1] = 0;
      dp[ar[i]][2] = 0;
    }
    long long int ma = 0, x;
    for (long long int i = 1; i < (n + 1); i++) {
      x = ar[i];
      if (dp[x][0] == 0) {
        if (dp[x - 1][0] == cnt[x - 1]) {
          dp[x][1] = dp[x - 1][1];
          dp[x][2] = dp[x - 1][1];
        } else {
          dp[x][1] = dp[x - 1][0];
        }
      }
      dp[x][2] = max(dp[x - 1][0], dp[x][2]);
      if (dp[x - 1][0] == cnt[x - 1]) {
        dp[x][2] = max(dp[x][2], dp[x - 1][1]);
      }
      for (long long int j = 0; j < (3); j++) {
        dp[x][j]++;
        ma = max(ma, dp[x][j]);
      }
    }
    cout << n - ma << '\n';
  }
}
