#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
constexpr int MX = 3e5 + 5;
int a[MX];
int main() {
  if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout);
  ios_base::sync_with_stdio(0), cin.tie(0);
  int q;
  cin >> q;
  while (q--) {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<int> v(a, a + n);
    sort(begin(v), end(v)), v.resize(unique(begin(v), end(v)) - begin(v));
    for (int i = 0; i < n; ++i)
      a[i] = lower_bound(begin(v), end(v), a[i]) - begin(v);
    set<ii> second, t;
    set<int> m;
    m.insert(a[0]);
    for (int i = 1; i < n; ++i) {
      auto it = m.upper_bound(a[i]);
      if (it != end(m)) second.emplace(a[i], *it), t.emplace(*it, a[i]);
      m.insert(a[i]);
    }
    int ans = (t.size() ? int(v.size() - begin(t)->first) : 0);
    for (int i = 0; i < v.size(); ++i) {
      while (second.size() && begin(second)->first == i)
        t.erase(ii(begin(second)->second, begin(second)->first)),
            second.erase(begin(second));
      ans = min(i + 1 + (t.size() ? int(v.size() - begin(t)->first) : 0), ans);
    }
    cout << ans << '\n';
  }
}
