#include <bits/stdc++.h>
using namespace std;
int a[200005];
int b[200005];
int dp[200005], last[200005], cnt[200005], all[200005], st[200005], ed[200005];
int main() {
  int t, n, m, ans;
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) b[i] = a[i];
    sort(b + 1, b + n + 1);
    m = unique(b + 1, b + n + 1) - b;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + m, a[i]) - b;
    for (int i = 1; i <= n; i++) ed[a[i]] = i;
    for (int i = n; i >= 1; i--) st[a[i]] = i;
    for (int i = 1; i <= n; i++) {
      dp[i] = max(dp[last[a[i]]], cnt[a[i] - 1]) + 1;
      if (i > ed[a[i] - 1]) dp[i] = max(dp[i], all[a[i] - 1] + 1);
      last[a[i]] = i;
      cnt[a[i]]++;
      if (i == ed[a[i]]) all[a[i]] = dp[st[a[i]]] + cnt[a[i]] - 1;
    }
    ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dp[i]);
    printf("%d\n", n - ans);
    for (int i = 1; i <= n; i++) dp[i] = 0;
    for (int i = 1; i <= n; i++) last[i] = 0;
    for (int i = 1; i <= n; i++) all[i] = 0;
    for (int i = 1; i <= n; i++) cnt[i] = 0;
  }
  return 0;
}
