#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const long long INF = 1e9 + 5;
const double eps = 1e-7;
const double PI = acos(-1.0);
inline void debug_vi(vector<int> a) {
  for (long long i = (long long)(0); i < (long long)(a.size()); i++)
    cout << a[i] << " ";
}
inline void debug_vll(vector<long long> a) {
  for (long long i = (long long)(0); i < (long long)(a.size()); i++)
    cout << a[i] << " ";
}
inline void print_case(int tn) { cout << "Case #" << tn << ": "; }
template <typename T>
using maxpq = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using minpq = priority_queue<T>;
const int N = 3e5 + 1;
int arr[N], minm[N];
set<int> s;
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int q, n;
  cin >> q;
  while (q--) {
    cin >> n;
    s.clear();
    for (long long i = (long long)(0); i < (long long)(n + 1); i++)
      minm[i] = INF;
    for (long long i = (long long)(0); i < (long long)(n); i++) {
      cin >> arr[i];
      auto itr = s.upper_bound(arr[i]);
      if (itr != s.end()) {
        minm[arr[i]] = min(*itr, minm[arr[i]]);
      }
      s.insert(arr[i]);
    }
    int sz = s.size();
    int elem[sz], ps[sz];
    int idx = 0;
    for (int e : s) {
      elem[idx] = e;
      ps[idx++] = minm[e];
    }
    int dp[sz + 1];
    dp[sz] = INF;
    for (long long i = (long long)(sz - 1); i >= (long long)(0); i--) {
      dp[i] = min(dp[i + 1], ps[i]);
    }
    int res = INF;
    for (long long l = (long long)(0); l < (long long)(sz); l++) {
      int pos = lower_bound(elem, elem + sz, dp[l]) - elem;
      int r = sz - pos;
      res = min(res, (int)l + r);
    }
    cout << res << "\n";
  }
  return 0;
}
