#include <bits/stdc++.h>
using namespace std;
inline char gc() {
  static const int L = 2333333;
  static char sxd[L], *sss = sxd, *ttt = sxd;
  if (sss == ttt) {
    ttt = (sss = sxd) + fread(sxd, 1, L, stdin);
    if (sss == ttt) {
      return EOF;
    }
  }
  return *sss++;
}
template <class T>
inline bool read(T& x) {
  x = 0;
  bool flg = false;
  char c = gc();
  for (; !isdigit(c); c = gc()) {
    if (c == '-') {
      flg = true;
    } else if (c == EOF) {
      return false;
    }
  }
  for (; isdigit(c); c = gc()) {
    x = (x * 10) + (c ^ 48);
  }
  if (flg) {
    x = -x;
  }
  return true;
}
template <class T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x >= 10) {
    write(x / 10);
    x %= 10;
  }
  putchar(x | 48);
}
const int maxn = 300005;
int n;
int aa[maxn];
int ll[maxn];
int rr[maxn];
int hv[maxn];
int qian[maxn];
int hou[maxn];
int ys[maxn];
inline void solve() {
  read(n);
  int cnt = 0;
  for (int i = 1; i <= n; ++i) {
    read(aa[i]);
    hv[aa[i]] = 1;
  }
  for (int i = 1; i <= n; ++i) {
    if (hv[i]) {
      ys[i] = ++cnt;
    }
  }
  for (int i = 1; i <= n; ++i) {
    aa[i] = ys[aa[i]];
  }
  for (int i = 1; i <= n; ++i) {
    if (!ll[aa[i]]) {
      ll[aa[i]] = rr[aa[i]] = i;
    } else {
      ll[aa[i]] = min(i, ll[aa[i]]);
      rr[aa[i]] = max(i, rr[aa[i]]);
    }
  }
  qian[1] = 0;
  for (int i = 2; i <= cnt; ++i) {
    if (rr[i - 1] <= ll[i]) {
      qian[i] = qian[i - 1];
    } else {
      qian[i] = i - 1;
    }
  }
  hou[cnt] = cnt + 1;
  for (int i = cnt - 1; i; --i) {
    if (rr[i] <= ll[i + 1]) {
      hou[i] = hou[i + 1];
    } else {
      hou[i] = i + 1;
    }
  }
  int ans = cnt;
  for (int i = 1; i <= cnt; ++i) {
    ans = min(ans, qian[i] + (cnt - hou[i] + 1));
  }
  write(ans);
  puts("");
  for (int i = 0; i <= n + 1; ++i) {
    ll[i] = rr[i] = hv[i] = qian[i] = hou[i] = ys[i] = 0;
  }
}
int main() {
  int T;
  read(T);
  while (T--) {
    solve();
  }
  return 0;
}
