#include <bits/stdc++.h>
using namespace std;
int power(int x, int y);
int mpower(int x, int y, int p);
int modInv(int a, int m);
int gcdExtended(int a, int b, int *x, int *y);
bool isPrime(int n);
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t, i, j, k, l, h, p, q, r, x, y, z, a, b, c, d, f, n, m, M = 1000000007;
  char ch, ch2, ch3;
  string s, s1, s2, s3;
  vector<int> w;
  set<int> S;
  cin >> t;
  while (t--) {
    unordered_map<int, int> N, F;
    cin >> n;
    int A[n], B[n], dp[n], ans[n + 5];
    vector<int> v[n + 5];
    for (i = 0; i < n; i++) {
      cin >> A[i];
      B[i] = A[i];
    }
    sort(B, B + n);
    c = 1;
    for (i = 0; i < n; i++) {
      if (!N[B[i]]) {
        N[B[i]] = c;
        c++;
      }
    }
    for (i = 0; i < n; i++) {
      p = N[A[i]];
      v[p].push_back(i);
    }
    for (i = n - 1; i >= 0; i--) {
      f = F[A[i]];
      c = N[A[i]];
      z = 1;
      if (f) {
        p = upper_bound(v[c].begin(), v[c].end(), i) - v[c].begin();
        z = 1 + dp[v[c][p]];
      }
      d = c + 1;
      if (v[d].size()) {
        p = v[d][0];
        if (p > i) {
          z = max(z, 1 + ans[d]);
        } else {
          p = v[d].end() - upper_bound(v[d].begin(), v[d].end(), i);
          z = max(z, 1 + p);
        }
      }
      dp[i] = z;
      if (i == v[c][0]) {
        p = v[c].size();
        ans[c] = dp[v[c][p - 1]] - 1 + p;
      }
      F[A[i]]++;
    }
    x = 0;
    for (i = 0; i < n; i++) {
      x = max(x, dp[i]);
    }
    cout << n - x << "\n";
  }
  return 0;
}
int modInv(int a, int m) {
  int x, y;
  int g = gcdExtended(a, m, &x, &y);
  int res = (x % m + m) % m;
  return res;
}
int gcdExtended(int a, int b, int *x, int *y) {
  if (a == 0) {
    *x = 0, *y = 1;
    return b;
  }
  int x1, y1;
  int gcd = gcdExtended(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
int mpower(int x, int y, int p) {
  int res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
int power(int x, int y) {
  int res = 1;
  while (y > 0) {
    if (y & 1) res = res * x;
    y = y >> 1;
    x = x * x;
  }
  return res;
}
bool isPrime(int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  int p = sqrt(n);
  for (int i = 5; i <= p; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
