#include <bits/stdc++.h>
using namespace std;
int n;
int fir[500200], F[500200], sum[500200];
int main() {
  int T;
  scanf("%d", &T);
  while (T-- > 0) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) sum[i] = 0, fir[i] = 0, F[i] = 0;
    for (int i = 1; i <= n; i++) {
      int t;
      scanf("%d", &t);
      if (!fir[t]) fir[t] = i;
      F[t] = i;
      sum[t] = 1;
    }
    int len = 0, all = 0, lst = 0, p = 0;
    for (int i = 1; i <= n; i++) {
      if (sum[i] == 0) continue;
      all += sum[i];
      if (lst < fir[i])
        len++;
      else
        len = 1;
      lst = F[i];
      p = max(p, len);
    }
    printf("%d\n", all - p);
  }
  return 0;
}
