#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
void solve() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < (N); ++i) cin >> A[i];
  vector<int> P = A;
  sort(P.begin(), P.end());
  P.erase(unique(P.begin(), P.end()), P.end());
  int cnt = 0;
  vector<int> val(N + 1, -1);
  for (int i = 0; i < P.size(); i++) val[P[i]] = cnt++;
  vector<int> lef(N + 1, -1), rig(N + 1, -1);
  for (int i = 0; i < N; i++) rig[val[A[i]]] = i;
  for (int i = N - 1; i >= 0; i--) lef[val[A[i]]] = i;
  int ans = N - 1;
  vector<int> ldp(cnt + 1, 0), rdp(cnt + 1, 0);
  int pre = 0;
  for (int i = 1; i < cnt; i++) {
    if (rig[i - 1] < lef[i])
      ldp[i] = pre;
    else
      ldp[i] = i;
    pre = ldp[i];
  }
  pre = 0;
  for (int i = cnt - 2; i >= 0; i--) {
    if (rig[i] < lef[i + 1])
      rdp[i] = pre;
    else
      rdp[i] = cnt - i - 1;
    pre = rdp[i];
  }
  ans = min(ldp[cnt - 1], rdp[0]);
  for (int i = 0; i < cnt - 1; i++) {
    if (rig[i] < lef[i + 1])
      ans = min(ans, ldp[i] + rdp[i + 1]);
    else
      ans = min(ans, min(i + 1 + rdp[i + 1], cnt - i - 1 + ldp[i]));
  }
  cout << ans << endl;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int Q;
  cin >> Q;
  for (int i = 0; i < (Q); ++i) solve();
  return 0;
}
