#include <bits/stdc++.h>
using namespace std;
int main() {
  int q;
  scanf("%d", &q);
  while (q--) {
    int n;
    scanf("%d", &n);
    int arr[n], sorted_arr[n];
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    memcpy(sorted_arr, arr, sizeof(arr));
    sort(sorted_arr, sorted_arr + n);
    unordered_map<int, int> reducer;
    int elems = 0;
    for (int i = 0; i < n; i++) {
      if (i == 0 || sorted_arr[i] != sorted_arr[i - 1]) {
        reducer[sorted_arr[i]] = elems;
        ++elems;
      }
    }
    for (int i = 0; i < n; i++) {
      arr[i] = reducer[arr[i]];
    }
    if (elems == 1) {
      printf("0\n");
      continue;
    }
    int locc[elems], rocc[elems];
    memset(locc, -1, sizeof(locc));
    memset(rocc, -1, sizeof(rocc));
    for (int i = 0; i < n; i++) {
      int idx = arr[i];
      if (locc[idx] == -1) locc[idx] = i;
      rocc[idx] = i;
    }
    int ans = elems;
    int j = 1;
    priority_queue<pair<int, int> > range_rocc;
    for (int i = 0; i < elems; i++) {
      if (i == j) j++;
      range_rocc.push({rocc[i], i});
      while (range_rocc.top().second < i) {
        range_rocc.pop();
      }
      while (locc[j] > range_rocc.top().first && j < elems) {
        range_rocc.push({rocc[j], j});
        j++;
      }
      int cand_ans = i + elems - j;
      ans = min(ans, cand_ans);
    }
    printf("%d\n", ans);
  }
}
