#include <bits/stdc++.h>
using namespace std;
int n, m, tot, ans;
int a[300010], num[300010];
int al[300010], ar[300010];
char s[300010];
inline void prework() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    num[i] = a[i];
  }
  sort(num + 1, num + 1 + n);
  tot = unique(num + 1, num + 1 + n) - num - 1;
  for (int i = 1; i <= n; i++) {
    a[i] = lower_bound(num + 1, num + 1 + tot, a[i]) - num;
    al[i] = 300010, ar[i] = 0;
  }
  for (int i = 1; i <= n; i++) {
    al[a[i]] = min(i, al[a[i]]);
    ar[a[i]] = max(i, ar[a[i]]);
  }
}
inline void mainwork() {
  ans = tot - 1;
  int mx = 0, cnt = 1;
  for (int i = 2; i <= tot; i++) {
    if (ar[i - 1] < al[i])
      cnt++;
    else
      mx = max(cnt, mx), cnt = 1;
  }
  mx = max(cnt, mx);
  ans = tot - mx;
}
inline void print() { printf("%d\n", ans); }
int main() {
  int t = 1;
  scanf("%d", &t);
  for (int i = 1; i <= t; i++) {
    prework();
    mainwork();
    print();
  }
  return 0;
}
