#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
const long long MOD = 1000000007;
int t, n, a[MAXN], dp[MAXN], L[MAXN], R[MAXN];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ;
  cin >> t;
  while (t--) {
    cin >> n;
    vector<int> val;
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
      val.emplace_back(a[i]);
    }
    sort(val.begin(), val.end());
    val.resize(unique(val.begin(), val.end()) - val.begin());
    int m = int(val.size());
    fill(L, L + m, n);
    fill(R, R + m, -1);
    for (int i = 0; i < n; i++) {
      a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
      R[a[i]] = max(R[a[i]], i);
      L[a[i]] = min(L[a[i]], i);
    }
    int ans = m - 1;
    dp[0] = 1;
    for (int i = 1; i < m; i++) {
      if (L[i] > R[i - 1]) {
        dp[i] = dp[i - 1] + 1;
      } else {
        dp[i] = 1;
      }
      ans = min(ans, m - dp[i]);
    }
    cout << ans << '\n';
  }
}
