#include <bits/stdc++.h>
#pragma GCC opatimize("unroll-loops")
using namespace std;
#pragma GCC diagnostic ignored "-Wmissing-declarations"
void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int& x : a) cin >> x;
  auto vals = a;
  sort(begin(vals), end(vals));
  vals.erase(unique(begin(vals), end(vals)), end(vals));
  for (int& x : a) x = lower_bound(begin(vals), end(vals), x) - begin(vals);
  vector<pair<int, int>> bord(vals.size(), {n + 1, 0});
  for (int i = 0; i < n; ++i) {
    bord[a[i]].first = min(bord[a[i]].first, i);
    bord[a[i]].second = max(bord[a[i]].second, i);
  }
  int ans = 1;
  int cnt = 1;
  for (size_t i = 1; i < bord.size(); ++i) {
    if (bord[i - 1].second < bord[i].first)
      ++cnt;
    else
      cnt = 1;
    ans = max(ans, cnt);
  }
  cout << bord.size() - ans << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int q;
  cin >> q;
  while (q--) solve();
}
