#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
int l[maxn], r[maxn], n;
int f[maxn], num[maxn], a[maxn];
vector<int> p;
int getid(int w) { return lower_bound(p.begin(), p.end(), w) - p.begin() + 1; }
int T;
int get(int w) {
  if (f[w] == w) return f[w];
  return f[w] = get(f[w]);
}
int main() {
  scanf("%d", &T);
  while (T--) {
    p.clear();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      p.push_back(a[i]);
    }
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    for (int i = 1; i <= p.size(); i++) {
      l[i] = n + 1;
      r[i] = 0;
      f[i] = i;
      num[i] = 1;
    }
    for (int i = 1; i <= n; i++) {
      a[i] = getid(a[i]);
      l[a[i]] = min(l[a[i]], i);
      r[a[i]] = max(r[a[i]], i);
    }
    for (int i = 2; i <= p.size(); i++) {
      if (l[i] > r[i - 1]) {
        get(i);
        get(i - 1);
        num[f[i]] += num[f[i - 1]];
        f[f[i - 1]] = f[i];
      }
    }
    int ans = p.size();
    for (int i = 1; i <= p.size(); i++) {
      if (f[i] == i) {
        ans = min(ans, (int)p.size() - num[i]);
      }
    }
    cout << ans << '\n';
  }
}
