#include <bits/stdc++.h>
using namespace std;
const long long N = 5e5 + 5;
inline long long read() {
  long long ret = 0, f = 0;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = 1;
    c = getchar();
  }
  while (isdigit(c)) {
    ret = ret * 10 + c - 48;
    c = getchar();
  }
  if (f) return -ret;
  return ret;
}
long long n, m, ans, a[N], L[N], R[N], b[N], c[N], f[N];
signed main() {
  long long T = read();
  while (T--) {
    n = read();
    for (long long i = 1; i <= n; i++) {
      a[i] = read();
      f[i] = 0;
      L[i] = 0;
      R[i] = 0;
    }
    for (long long i = n; i; i--) L[a[i]] = i;
    for (long long i = 1; i <= n; i++) R[a[i]] = i;
    long long m = 0;
    for (long long i = 1; i <= n; i++)
      if (L[i]) b[++m] = i;
    sort(b + 1, b + m + 1);
    for (long long i = 1; i <= m; i++) c[b[i]] = b[i - 1];
    ans = 1;
    f[b[1]] = 1;
    for (long long i = 2; i <= m; i++) {
      if (R[b[i - 1]] < L[b[i]])
        f[b[i]] = f[b[i - 1]] + 1;
      else
        f[b[i]] = 1;
      ans = max(ans, f[b[i]]);
    }
    printf("%lld\n", m - ans);
  }
}
