#include <bits/stdc++.h>
using namespace std;
int in(char &c) { return scanf("%c", &c); }
int in(char s[]) { return scanf("%s", s); }
int in(int &x) { return scanf("%d", &x); }
int in(long long &x) { return scanf("%lld", &x); }
int in(double &x) { return scanf("%lf", &x); }
int in(pair<int, int> &p) { return scanf("%d%d", &p.first, &p.second); }
int in(pair<long long, long long> &p) {
  return scanf("%lld%lld", &p.first, &p.second);
}
int in(pair<double, double> &p) { return scanf("%lf%lf", &p.first, &p.second); }
int in(long double &a) { return scanf("%Lf", &a); }
int in(int &x, long long &y) { return scanf("%d%lld", &x, &y); }
int in(long long &x, int &y) { return scanf("%lld%d", &x, &y); }
int in(int &x, int &y) { return scanf("%d%d", &x, &y); }
int in(long long &x, long long &y) { return scanf("%lld%lld", &x, &y); }
int in(int &n, char s[]) { return scanf("%d%d", &n, s); }
int in(char a[], char b[]) { return scanf("%s%s", a, b); }
int in(double &x, double &y) { return scanf("%lf%lf", &x, &y); }
int in(int &x, int &y, int &z) { return scanf("%d%d%d", &x, &y, &z); }
int in(long long &x, long long &y, long long &z) {
  return scanf("%lld%lld%lld", &x, &y, &z);
}
int in(double &x, double &y, double &z) {
  return scanf("%lf%lf%lf", &x, &y, &z);
}
int in(int &x, int &y, int &z, int &k) {
  return scanf("%d%d%d%d", &x, &y, &z, &k);
}
int in(long long &x, long long &y, long long &z, long long &k) {
  return scanf("%lld%lld%lld%lld", &x, &y, &z, &k);
}
int in(double &x, double &y, double &z, double &k) {
  return scanf("%lf%lf%lf%lf", &x, &y, &z, &k);
}
const int N = 3e5 + 10, M = 1e3 + 10, mod = 1e9 + 7;
const double eps = 1e-6, Pi = acos(-1.0);
int a[N], b[N], L[N], R[N], s[N];
vector<int> vc[N];
int check(int x, int y) { return (L[y] > R[x]); }
int query(int x, int p) {
  x = max(0, x);
  p = max(0, p);
  int pos = upper_bound(vc[x].begin(), vc[x].end(), p) - vc[x].begin();
  return pos;
}
int main() {
  int T, t;
  in(T);
  t = T;
  while (T--) {
    int n;
    in(n);
    for (int i = 1; i <= n; i++) {
      in(a[i]);
      b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    int m = unique(b + 1, b + 1 + n) - b;
    for (int i = 1; i <= n; i++)
      a[i] = lower_bound(b + 1, b + m, a[i]) - b, s[a[i]]++,
      vc[a[i]].push_back(i);
    for (int i = n; i >= 1; i--) L[a[i]] = i;
    for (int i = 1; i <= n; i++) s[i] += s[i - 1], R[a[i]] = i;
    m--;
    int l, r, ans = 0;
    l = r = 1;
    L[m + 1] = L[m];
    R[m + 1] = R[m];
    for (int i = 1; i <= m; i++) {
      while (r <= m && check(r, r + 1)) r++;
      int t = query(l - 1, L[l]) + (int)vc[r + 1].size() - query(r + 1, R[r]);
      ans = max(ans, s[r] - s[l - 1] + t);
      if (l == r) {
        for (int j = 0; j < vc[l].size(); j++) {
          ans = max(ans, (int)vc[l].size() + query(l - 1, vc[l][j]) - j);
        }
      }
      ans = max(ans, s[r] - s[l - 1] + query(l - 1, L[l]));
      if (r == m) break;
      l = r + 1;
      r++;
    }
    printf("%d\n", n - ans);
    for (int i = 1; i <= n; i++) s[i] = 0, vc[i].clear();
  }
  return 0;
}
