#include <bits/stdc++.h>
using namespace std;
using namespace std;
int a[300010];
int l[300010], r[300010];
int main() {
  int t, n, i;
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    for (i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (i = 1; i <= n; i++) r[a[i]] = i;
    for (i = n; i >= 1; i--) l[a[i]] = i;
    int last, ma, ans, num;
    last = ma = ans = num = 0;
    for (i = 1; i <= n; i++) {
      if (l[i]) {
        if (last < l[i])
          ma++;
        else
          ma = 1;
        num++;
        ans = max(ans, ma);
        last = r[i];
      }
      l[i] = 0;
    }
    printf("%d\n", num - ans);
  }
}
