#include <bits/stdc++.h>
using namespace std;
const long long big = 2e9 + 5;
const long long md = 1e9 + 7;
const long long steps[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
struct fenw {
 private:
  vector<int> a;
  int n;

 public:
  void build(int N) {
    n = N;
    a.resize(n);
    for (int i = 0; i < n; i++) a[i] = 0;
  }
  void baff(int x, int c) {
    for (; x < n; x = (x | (x - 1)) + 1) a[x] = max(a[x], c);
  }
  int ask(int x) {
    int res = 0;
    for (; x > 0; x &= x - 1) res = max(res, a[x]);
    return res;
  }
};
void solve();
int main() {
  ios_base ::sync_with_stdio(0);
  cin.tie();
  cout.tie();
  long long q;
  cin >> q;
  for (; q > 0; q--) {
    solve();
  }
  return 0;
}
fenw tree;
int n;
int l[1000000];
int r[1000000];
int a[1000000];
vector<int> q;
void solve() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    l[i] = -1;
    r[i] = -1;
  }
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (l[a[i]] == -1) l[a[i]] = i + 4;
    r[a[i]] = max(r[a[i]], i + 4);
  }
  int res = 0, ans = 0;
  q.clear();
  for (int i = 1; i <= n; i++) {
    if (l[i] == -1) continue;
    res++;
    q.push_back(i);
  }
  bool bad = false;
  for (int i = 1; i < n; i++) {
    if (a[i] >= a[i - 1]) continue;
    bad = true;
  }
  if (!bad) {
    cout << 0 << endl;
    return;
  }
  int L = 0, R = 0;
  while (R < res) {
    R++;
    while (R < res && l[q[R]] > r[q[R - 1]]) R++;
    ans = max(ans, R - L);
    L = R;
  }
  cout << res - ans << endl;
}
