#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
void print() {}
template <class H, class... T>
void print(H&& h, T&&... t) {
  cout << h << " \n"[sizeof...(t) == 0];
  print(forward<T>(t)...);
}
vector<long long> compress(vector<long long> x, long long n) {
  vector<long long> v;
  v.push_back(-INF);
  v.push_back(INF);
  for (long long i = (0); i < (n); i++) v.push_back(x[i]);
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  vector<long long> res;
  for (long long i = (0); i < (n); i++)
    res.push_back(lower_bound(v.begin(), v.end(), x[i]) - v.begin());
  return res;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long Q;
  cin >> Q;
  while (Q--) {
    long long N;
    cin >> N;
    vector<long long> a(N);
    for (long long i = (0); i < (N); i++) cin >> a[i];
    a = compress(a, N);
    long long max_val = 0;
    for (long long i = (0); i < (N); i++) max_val = max(max_val, a[i]);
    vector<long long> top(N + 1, -1), back(N + 1, -1);
    for (long long i = (0); i < (N); i++) {
      if (top[a[i]] == -1) {
        top[a[i]] = i;
      }
    }
    for (long long i = (N - 1); i >= (0); i--) {
      if (back[a[i]] == -1) {
        back[a[i]] = i;
      }
    }
    vector<long long> sum(N + 2, 0);
    for (long long i = (0); i < (max_val - 1); i++) {
      if (back[i + 1] < top[i + 2]) {
        sum[i + 1] = 1;
      }
    }
    for (long long i = (0); i < (N + 1); i++) sum[i + 1] += sum[i];
    long long ans = 0;
    for (long long i = (1); i < (max_val + 1); i++) {
      if (sum[i] - sum[i - 1] == 0) continue;
      long long lv = i, rv = max_val + 1;
      while (rv - lv > 1) {
        long long mid = (rv + lv) / 2;
        long long v = sum[mid] - sum[i - 1];
        if (mid - i + 1 == v) {
          lv = mid;
        } else {
          rv = mid;
        }
      }
      ans = max(ans, lv - i + 1);
    }
    ans = max_val - (ans + 1);
    print(ans);
  }
}
