#include <bits/stdc++.h>
using namespace std;
int x[300100], a[300100], n, l[300100], nn, r[300100];
int find(int v) {
  int h = 1, t = nn, r = 0, m;
  while (h <= t)
    if (x[m = h + t >> 1] <= v)
      r = m, h = m + 1;
    else
      t = m - 1;
  return r;
}
int main() {
  int _;
  scanf("%d", &_);
  while (_--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), x[i] = a[i];
    sort(x + 1, x + n + 1);
    for (int i = 1; i <= n; ++i)
      if (i == 1)
        nn = 1;
      else if (x[i] ^ x[i - 1])
        x[++nn] = x[i];
    for (int i = 1; i <= nn; ++i) l[i] = n + 1, r[i] = 0;
    for (int i = 1; i <= n; ++i)
      a[i] = find(a[i]), l[a[i]] = min(l[a[i]], i), r[a[i]] = max(r[a[i]], i);
    int mx = 1;
    for (int i = 2, ls = 1; i <= nn; ++i) {
      if (l[i] <= r[i - 1])
        ls = 1;
      else
        ++ls;
      mx = max(mx, ls);
    }
    printf("%d\n", nn - mx);
  }
}
