#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int main() {
  ios::sync_with_stdio(false), cin.tie(), cout.tie();
  int q;
  cin >> q;
  while (q--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i], a[i]--;
    vector<bool> cnt(n, false);
    vector<int> minidx(n, n + 1);
    vector<int> maxidx(n, -1);
    for (int i = 0; i < n; i++) {
      int cur = a[i];
      cnt[cur] = true;
      maxidx[cur] = max(maxidx[cur], i);
      minidx[cur] = min(minidx[cur], i);
    }
    vector<int> v;
    for (int i = 0; i < n; i++) {
      if (cnt[i] == false) continue;
      v.push_back(i);
    }
    vector<int> dp(n, 0);
    int res = n;
    for (int i = v.size() - 1; i >= 0; i--) {
      if (i + 1 == v.size() || maxidx[v[i]] >= minidx[v[i + 1]])
        dp[i] = 1;
      else
        dp[i] = 1 + dp[i + 1];
      res = min(res, int(v.size()) - dp[i]);
    }
    cout << res << endl;
  }
}
