#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
const long long MAXK = 19;
const long long MAXN = 4e5;
vector<long long> t;
long long LOG[MAXN];
void mod1(long long v, long long vl, long long vr, long long x) {
  if (vl == vr - 1) {
    t[v] = vl;
    return;
  }
  long long vm = (vl + vr) / 2;
  if (x < vm) {
    mod1(2 * v + 1, vl, vm, x);
  } else {
    mod1(2 * v + 2, vm, vr, x);
  }
  t[v] = max(t[2 * v + 1], t[2 * v + 2]);
}
long long get1(long long v, long long vl, long long vr, long long x) {
  if (vl == vr - 1) {
    return vl;
  }
  long long vm = (vl + vr) / 2;
  if (t[2 * v + 1] > x) {
    return get1(2 * v + 1, vl, vm, x);
  }
  if (t[2 * v + 2] > x) {
    return get1(2 * v + 2, vm, vr, x);
  }
  return INF;
}
vector<vector<long long>> st;
void build(vector<long long> &a) {
  long long n = a.size();
  st.resize(n);
  for (auto &c : st) {
    c.resize(MAXK);
  }
  for (long long i = 0; i < n; i++) {
    st[i][0] = a[i];
  }
  for (long long k = 1; k < MAXK; k++) {
    for (long long i = 0; i + (1 << k) - 1 < n; i++) {
      st[i][k] = min(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
    }
  }
}
long long get(long long l, long long r) {
  long long k = LOG[r - l];
  return min(st[l][k], st[r - (1 << k)][k]);
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  LOG[1] = 0;
  for (long long i = 2; i < MAXN; i++) {
    LOG[i] = LOG[i / 2] + 1;
  }
  long long q;
  cin >> q;
  while (q--) {
    long long n;
    cin >> n;
    vector<long long> a(n);
    set<long long> h;
    for (auto &c : a) {
      cin >> c;
      h.insert(c);
    }
    t.assign(4 * n + 20, -1);
    vector<long long> last(n + 10);
    for (long long i = 0; i < n; i++) {
      last[a[i]] = i;
    }
    vector<long long> b(n + 2, INF);
    for (long long i = 0; i < n; i++) {
      if (i == last[a[i]]) {
        long long res = get1(0, 0, n + 2, a[i]);
        b[a[i]] = res;
      }
      mod1(0, 0, n + 2, a[i]);
    }
    build(b);
    vector<long long> f;
    for (auto &c : h) {
      f.push_back(c);
    }
    vector<long long> s = f;
    reverse(f.begin(), f.end());
    long long mx = -1;
    vector<long long> pos(n + 10);
    for (long long i = 0; i < s.size(); i++) {
      pos[s[i]] = i;
    }
    long long ans = INF;
    for (long long i = f.size(); i >= 0; i--) {
      if (i < f.size()) {
        mx = max(mx, pos[f[i]]);
      }
      long long l = 0;
      if (i < f.size()) {
        l = f[i] + 1;
      }
      if (get(l, n + 2) == INF) {
        ans = min(ans, (long long)f.size() - i);
        continue;
      }
      long long left = mx, right = s.size();
      while (right - left > 1) {
        long long mid = (left + right) / 2;
        long long l = 0;
        if (i < f.size()) {
          l = f[i] + 1;
        }
        long long r = s[mid];
        if (get(l, r) >= r) {
          left = mid;
        } else {
          right = mid;
        }
      }
      if (left == mx) {
        continue;
      } else {
        ans = min(ans, (long long)f.size() - i + (long long)s.size() - left);
      }
    }
    cout << ans << "\n";
  }
  return 0;
}
