#include <bits/stdc++.h>
using namespace std;
const double PI = 3.14159265358979323846;
const double eps = (1e-5);
int isGreater(long double x, long double y) {
  if (abs(x - y) < eps) return 0;
  if (x > y) return 1;
  return -1;
}
int n, e;
const int MAX_N = 3e5 + 5;
int first[MAX_N], last[MAX_N], a[MAX_N], visit[MAX_N], vid;
void compress() {
  ++vid;
  e = 0;
  map<int, int> after;
  for (int i = 0; i < n; ++i) after[a[i]];
  for (auto &item : after) item.second = e++;
  for (int i = 0; i < n; ++i) {
    a[i] = after[a[i]];
    if (visit[a[i]] != vid) {
      first[a[i]] = i;
      visit[a[i]] = vid;
    }
    last[a[i]] = i;
  }
}
int mem[MAX_N];
int f(int x) {
  if (x == e) return 0;
  int &ret = mem[x];
  if (visit[x] == vid) return ret;
  visit[x] = vid;
  ret = 1;
  if (last[x] < first[x + 1]) ret += f(x + 1);
  return ret;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tc;
  cin >> tc;
  while (tc--) {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    compress();
    int ans = 0;
    ++vid;
    for (int x = 0; x <= e; ++x) ans = max(ans, f(x));
    cout << e - ans << '\n';
  }
  return 0;
}
