#include <bits/stdc++.h>
using namespace std;
void setIO(const string &name = "") {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  if (name.length()) {
    freopen((name + ".in").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
  }
}
template <typename T>
void read(vector<T> &a) {
  for (auto &x : a) cin >> x;
}
template <typename T>
void read(vector<T> &a, int n) {
  a.resize(n);
  for (auto &x : a) cin >> x;
}
template <class T, class U>
ostream &operator<<(ostream &out, const pair<T, U> &v) {
  out << "(";
  out << v.first << "," << v.second;
  return out << ")";
}
template <class T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << "[";
  for (auto(i) = 0; i < (int)(v).size(); i++) {
    if (i) out << ", ";
    out << v[i];
  }
  return out << "]";
}
template <typename T>
void print(vector<T> &a) {
  for (const auto &x : a) cout << x << ' ';
  cout << '\n';
}
void MOD(int &x, int m = 1000000007) {
  x %= m;
  if (x < 0) x += m;
}
template <typename T>
void dbg(const char *name, T &&arg1) {
  cout << name << " : " << arg1 << '\n';
}
template <typename T, typename... U>
void dbg(const char *names, T &&arg1, U &&...args) {
  const char *comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  dbg(comma + 1, args...);
}
template <class T>
void read(T &x) {
  cin >> x;
}
template <class T, class... U>
void read(T &t, U &...u) {
  read(t);
  read(u...);
}
int gcd(int a, int b) { return !a ? b : gcd(b % a, a); }
int n;
vector<long long> a;
vector<long long> starting, ending;
void solve() {
  read(n);
  read(a, n);
  starting.assign(n + 2, -1);
  ending.assign(n + 2, -1);
  for (auto(i) = 0; i < n; i++) {
    if (starting[a[i]] == -1) {
      starting[a[i]] = i;
      ending[a[i]] = i;
    } else {
      ending[a[i]] = i;
    }
  }
  vector<long long> c = a;
  sort(c.begin(), c.end());
  c.erase(unique(c.begin(), c.end()), c.end());
  vector<long long> range;
  range.reserve(n);
  int sz = 1;
  for (auto(i) = 1; i < (int)(c).size(); i++) {
    if (starting[c[i]] < ending[c[i - 1]]) {
      range.emplace_back(sz);
      sz = 1;
    } else
      sz++;
  }
  range.emplace_back(sz);
  int ans = (int)(c).size() - *max_element(range.begin(), range.end());
  cout << ans << '\n';
}
int32_t main() {
  setIO();
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
