#include <bits/stdc++.h>
const int MAXN = 3e5 + 10;
const double eps = 1e-8;
const int inf = 1e9 + 9;
using namespace std;
struct edge {
  int t, v;
  edge *next;
} e[MAXN << 1], *h[MAXN], *o = e;
void add(int x, int y, int vul) {
  o->t = y;
  o->v = vul;
  o->next = h[x];
  h[x] = o++;
}
long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x * f;
}
int _, n, a[MAXN], b[MAXN];
vector<int> vec;
int last[MAXN];
int minn[MAXN], maxx[MAXN];
int Left[MAXN], num[MAXN], dp2[MAXN], dp[MAXN];
int main() {
  _ = read();
  while (_--) {
    n = read();
    vec.clear();
    for (int i = 1; i <= n; i++) a[i] = read(), vec.push_back(a[i]);
    sort(vec.begin(), vec.end());
    int sz = unique(vec.begin(), vec.end()) - vec.begin();
    for (int i = 1; i <= n; i++) {
      a[i] = lower_bound(vec.begin(), vec.begin() + sz, a[i]) - vec.begin() + 1;
    }
    for (int i = 1; i <= n; i++) last[i] = num[i] = 0;
    for (int i = 1; i <= n; i++) {
      Left[i] = num[a[i] - 1];
      num[a[i]]++;
      last[a[i]] = i;
    }
    for (int i = 1; i <= n; i++) minn[i] = n + 1, maxx[i] = 0;
    for (int i = 1; i <= n; i++) {
      minn[a[i]] = min(minn[a[i]], i);
      maxx[a[i]] = max(maxx[a[i]], i);
    }
    for (int i = 1; i <= n; i++) dp2[i] = 0;
    dp2[1] = num[1];
    for (int i = 2; i <= sz; i++) {
      if (maxx[i - 1] < minn[i])
        dp2[i] = dp2[i - 1] + num[i];
      else
        dp2[i] = num[i] + Left[minn[i]];
    }
    for (int i = 1; i <= n; i++) last[i] = dp[i] = 0;
    int ans = inf;
    for (int i = 1; i <= n; i++) {
      int x = 0;
      if (maxx[a[i] - 1] < i)
        x = dp2[a[i] - 1] + 1;
      else
        x = Left[i] + 1;
      dp[i] = max(x, dp[last[a[i]]] + 1);
      last[a[i]] = i;
      ans = min(ans, n - dp[i]);
    }
    printf("%d\n", ans);
  }
  return 0;
}
