#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
  return os << "(" << x.first << "," << x.second << ")";
}
int main() {
  int q;
  scanf("%d", &q);
  while (q--) {
    int n;
    scanf("%d", &n);
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
      scanf("%d", &a[i]);
      b[i] = a[i];
    }
    sort(b.begin(), b.end());
    b.resize(unique(b.begin(), b.end()) - b.begin());
    for (int i = 0; i < n; ++i) {
      a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
    }
    int m = b.size();
    vector<int> st(m, -1), en(m, -1), f(m);
    for (int i = 0; i < n; ++i) {
      if (st[a[i]] == -1) st[a[i]] = i;
      en[a[i]] = i;
    }
    int ans = m;
    for (int i = m - 1; i >= 0; --i) {
      f[i] = 1;
      if (i != m - 1 && st[i + 1] > en[i]) f[i] += f[i + 1];
      ans = min(ans, m - f[i]);
    }
    printf("%d\n", ans);
  }
}
