#include <bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
const long long INF = 2e18;
const int maxn = 1e6 + 6;
const int mod = 1e9 + 6;
const double eps = 1e-15;
inline bool read(long long &num) {
  char in;
  bool IsN = false;
  in = getchar();
  if (in == EOF) return false;
  while (in != '-' && (in < '0' || in > '9')) in = getchar();
  if (in == '-') {
    IsN = true;
    num = 0;
  } else
    num = in - '0';
  while (in = getchar(), in >= '0' && in <= '9') {
    num *= 10, num += in - '0';
  }
  if (IsN) num = -num;
  return true;
}
long long n, m, p;
long long num[maxn];
vector<long long> v;
int vis[maxn];
int getid(long long x) {
  return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
long long dp[maxn][2];
long long pre[maxn], first[maxn], sc[maxn];
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    read(n);
    v.clear();
    for (int i = 1; i <= n; i++) {
      vis[i] = 0;
      dp[i][0] = dp[i][1] = 0;
      pre[i] = 0;
      first[i] = 0;
      sc[i] = -(1e9 + 7);
    }
    for (int i = 1; i <= n; i++) {
      read(num[i]);
      v.push_back(num[i]);
    }
    long long maxl = 0;
    sort(v.begin(), v.end());
    v.erase((unique(v.begin(), v.end())), v.end());
    for (int i = 1; i <= n; i++) vis[getid(num[i])]++;
    for (int i = 1; i <= n; i++) {
      int id = getid(num[i]);
      pre[id]++;
      dp[id][0] = dp[id][0] + 1;
      if (pre[id] == 1) first[id] = max(dp[id - 1][0], dp[id - 1][1]);
      if (pre[id] == vis[id]) dp[id][1] = first[id] + vis[id];
      sc[id] =
          max(sc[id], max(dp[id - 1][0] - pre[id], dp[id - 1][1] - pre[id]));
      maxl = max(maxl, sc[id] + pre[id] + 1);
      maxl = max(maxl, max(dp[id][0], dp[id][1]));
    }
    printf("%lld\n", n - maxl);
  }
  return 0;
}
