#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int q, n, a[N], b[N], t[N];
struct node {
  int x, y;
} l[N];
int f[N];
int read() {
  int x, f = 1;
  char ch;
  while ((ch = getchar()) < '0' || ch > '9')
    if (ch == '-') f = -1;
  x = ch ^ 48;
  while ((ch = getchar()) >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + (ch ^ 48);
  return x * f;
}
int main() {
  q = read();
  while (q--) {
    for (int i = 1; i <= n; i++) l[i] = {0, 0}, f[i] = 0;
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read(), b[i] = a[i];
    sort(b + 1, b + n + 1);
    int sz = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= sz; i++) t[b[i]] = i;
    for (int i = 1; i <= n; i++) a[i] = t[a[i]];
    for (int i = 1; i <= n; i++)
      if (l[a[i]].x == 0) l[a[i]].x = i;
    for (int i = n; i >= 1; i--)
      if (l[a[i]].y == 0) l[a[i]].y = i;
    int ret = 0;
    for (int i = 1; i <= sz; i++) {
      if (l[i - 1].y < l[i].x)
        f[i] = f[i - 1] + 1;
      else
        f[i] = 1;
      ret = max(ret, f[i]);
    }
    printf("%d\n", sz - ret);
  }
  return 0;
}
