#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int arr[maxn], dp[maxn], cnt[maxn], las[maxn], num[maxn], fir[maxn];
int v[maxn], cntv;
int n;
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    fill(dp + 1, dp + 1 + n, 0);
    fill(cnt + 1, cnt + 1 + n, 0);
    fill(las + 1, las + 1 + n, 0);
    fill(num + 1, num + 1 + n, 0);
    fill(fir + 1, fir + 1 + n, 0);
    cntv = 0;
    for (int i = 1; i <= n; i++) {
      scanf("%d", &arr[i]);
      v[++cntv] = arr[i];
    }
    sort(v + 1, v + 1 + cntv);
    cntv = unique(v + 1, v + 1 + cntv) - v - 1;
    for (int i = 1; i <= n; i++) {
      arr[i] = lower_bound(v + 1, v + 1 + cntv, arr[i]) - v;
      ++num[arr[i]];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
      int x = arr[i];
      dp[i] = cnt[x - 1] + 1;
      if (las[x]) dp[i] = max(dp[i], dp[las[x]] + 1);
      if (num[x - 1] == cnt[x - 1])
        dp[i] = max(dp[i], dp[fir[x - 1]] + cnt[x - 1]);
      if (!fir[x]) fir[x] = i;
      las[x] = i;
      ++cnt[x];
      ans = max(ans, dp[i]);
    }
    printf("%d\n", n - ans);
  }
  return 0;
}
