#include <bits/stdc++.h>
const int maxn = 3e5 + 3;
int n, a[maxn], b[maxn], m, l[maxn], r[maxn];
void solve() {
  scanf("%d", &n);
  m = 0;
  for (int i = 0; i < n; ++i) {
    scanf("%d", a + i);
    b[m++] = a[i];
  }
  std::sort(b, b + m);
  m = std::unique(b, b + m) - b;
  for (int i = 0; i < n; ++i) {
    a[i] = std::lower_bound(b, b + m, a[i]) - b;
  }
  std::fill(l, l + m, 0x7fffffff);
  std::fill(r, r + m, 0x80000000);
  for (int i = 0; i < n; ++i) {
    l[a[i]] = std::min(l[a[i]], i);
    r[a[i]] = std::max(r[a[i]], i);
  }
  int ans = m - 1;
  for (int i = 0, j; i < m; i = j) {
    for (j = i + 1; j < m && r[j - 1] < l[j]; ++j)
      ;
    ans = std::min(ans, i + (m - j));
  }
  printf("%d\n", ans);
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) solve();
  return 0;
}
