#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5 + 10;
const long long mod = 1e9 + 7;
const bool debug = false;
template <class T>
inline void add(T &x, long long y) {
  x += y;
  if (x >= mod) x -= mod;
}
template <class T>
inline void del(T &x, long long y) {
  x -= y;
  if (x < 0) x += mod;
}
template <class T>
inline void add(T &x, long long y, long long z) {
  x = y + z;
  if (x >= mod) x -= mod;
}
inline long long qpow(long long x, long long y) {
  x %= mod;
  long long ret = 1;
  while (y) {
    if (y & 1) ret = ret * x % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ret;
}
inline long long qmul(long long x, long long y, long long mod) {
  return ((x * y - (long long)((long double)x * y / mod) * mod) + mod) % mod;
}
inline long long gcd(long long x, long long y) { return x ? gcd(y % x, x) : y; }
inline long long lcm(long long x, long long y) { return x / gcd(x, y) * y; }
int v[N], l[N], cnt[N], ok[N];
void solve() {
  int n, nn = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) l[i] = cnt[i] = 0;
  for (int i = 1; i <= n; ++i) scanf("%d", &v[i]), cnt[v[i]]++;
  for (int i = 1, pre = 0; i <= n; ++i)
    if (cnt[i]) l[i] = pre, ok[i] = (pre != 0), pre = i, nn++;
  int mx = 0, now = 0;
  for (int i = 1; i <= n; ++i) {
    if (cnt[l[v[i]]]) ok[v[i]] = 0;
    cnt[v[i]]--;
  }
  for (int i = 1; i <= n; ++i) {
    if (l[i]) {
      if (ok[i])
        now++;
      else
        mx = max(mx, now + 1), now = 0;
    }
  }
  mx = max(mx, now + 1);
  printf("%d\n", nn - mx);
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) solve();
  return 0;
}
