#include <bits/stdc++.h>
using namespace std;
int64_t mod = 998244353;
int64_t mod1 = 998244353;
int64_t power(int64_t a, int64_t b) {
  if (b == 0)
    return 1;
  else if (b % 2 == 0)
    return power(((((a) % mod) * ((a) % mod)) % mod), b / 2) % mod;
  else
    return (((a) % mod) *
            (power(((((a) % mod) * ((a) % mod)) % mod), b / 2) % mod)) %
           mod;
}
inline int64_t inverse(int64_t a, int64_t md) {
  a %= md;
  if (a < 0) a += md;
  int64_t b = md, u = 0, v = 1;
  while (a) {
    int64_t t = b / a;
    b -= t * a;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  assert(b == 1);
  if (u < 0) u += md;
  return u;
}
const int64_t ce = 998244353;
int64_t fast_mod(int64_t input) { return input < ce ? input : input % ce; }
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int64_t t;
  cin >> t;
  while (t--) {
    int64_t n;
    cin >> n;
    int64_t a[n + 1];
    map<int64_t, int64_t> m;
    set<int64_t> s;
    for (int64_t i = 1; i <= n; i++) cin >> a[i], s.insert(a[i]);
    int64_t c = 1;
    for (auto i : s) m[i] = c, c++;
    c--;
    for (int64_t i = 1; i <= n; i++) a[i] = m[a[i]];
    int64_t fi[c + 1];
    memset(fi, -1, sizeof(fi));
    int64_t la[c + 1];
    memset(la, -1, sizeof(la));
    for (int64_t i = 1; i <= n; i++) {
      if (fi[a[i]] == -1) {
        fi[a[i]] = i;
      }
      la[a[i]] = max(la[a[i]], i);
    }
    int64_t pk[c + 1];
    int64_t pk1[c + 1];
    for (int64_t i = 1; i <= c; i++) {
      int64_t st = i;
      int64_t p = 1;
      for (int64_t j = i + 1; j <= c; j++) {
        if (la[j - 1] <= fi[j]) {
          p++;
          if (j == c) i = c;
          continue;
        } else {
          i = j - 1;
          break;
        }
      }
      for (int64_t k = st; k <= i; k++) {
        pk[k] = p;
        p--;
      }
    }
    for (int64_t i = c; i >= 1; --i) {
      int64_t p = 1;
      int64_t st = i;
      for (int64_t j = i - 1; j >= 1; --j) {
        if (la[j] <= fi[j + 1]) {
          p++;
          if (j == 1) i = 1;
        } else {
          i = j + 1;
          break;
        }
      }
      for (int64_t k = st; k >= i; --k) {
        pk1[k] = p;
        p--;
      }
    }
    int64_t ans = c - 1;
    ans = min(ans, c - pk[1]);
    ans = min(ans, c - pk1[c]);
    for (int64_t i = 1; i < c; i++) {
      if (la[i] <= fi[i + 1])
        ans = min(ans, i - pk1[i] + (c - i) - pk[i + 1]);
      else {
        ans = min(ans, i - pk1[i] + c - i);
        ans = min(ans, (c - i) + pk[i] + i);
      }
    }
    cout << ans << '\n';
  }
}
