#include <bits/stdc++.h>
using namespace std;
int main() {
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    int a[n];
    pair<int, int> b[n];
    set<int> S;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      S.insert(a[i]);
    }
    map<int, int> M;
    int idx = 0;
    for (int x : S) {
      M.insert({x, idx++});
    }
    int left[n + 1], right[n + 1], count[n + 1];
    memset(left, -1, sizeof(left));
    memset(count, 0, sizeof(count));
    for (int i = 0; i < n; i++) {
      a[i] = M[a[i]];
      b[i] = {a[i], -1 * i};
      if (left[a[i]] == -1) {
        left[a[i]] = i;
      }
      right[a[i]] = i;
      count[a[i]]++;
    }
    sort(b, b + n);
    int dp[n + 1];
    memset(dp, 0, sizeof(dp));
    for (int i = n - 1; i >= 0; i--) {
      dp[i] = 1;
      if (left[a[i] + 1] != -1) {
        if (left[a[i] + 1] > i) {
          dp[i] = max(dp[i], dp[right[a[i] + 1]] + (count[a[i] + 1]));
        }
      }
    }
    for (int i = 0; i < n; i++) {
    }
    int current_count = 0, ans = n - dp[b[0].first];
    for (int i = -1; i < n; i++) {
      if (i > 0 && b[i].first == b[i - 1].first) {
        current_count++;
      } else {
        current_count = 1;
      }
      int rem = 0;
      if (i == -1) {
        rem = dp[-1 * b[0].second] + (count[b[0].first] - 1);
      } else if (i + 1 < n && b[i].first == b[i + 1].first) {
        rem = dp[-1 * b[i + 1].second] +
              max((int)0, count[b[i].first] - (current_count + 1));
      } else if (i + 1 < n && b[i].first != b[i + 1].first) {
        rem = dp[right[b[i + 1].first]] + count[b[i + 1].first] - 1;
      }
      ans = min(ans, n - rem);
    }
    cout << ans << endl;
  }
}
