#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,fma,sse2,sse3,ssse3,sse4,tune=native")
using namespace std;
const long long mod = 998244353;
mt19937 rng((int)chrono::steady_clock::now().time_since_epoch().count());
const int mxN = 200010;
int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) {
    int N;
    cin >> N;
    vector<long long> p(N);
    for (int i = 0; i < N; i++) cin >> p[i];
    vector<long long> need(N + 2);
    vector<long long> mn(N + 2, INT_MIN);
    vector<long long> df = p;
    sort(df.begin(), df.end());
    df.erase(unique(df.begin(), df.end()), df.end());
    for (int i = 0; i < N; i++) {
      p[i] = lower_bound(df.begin(), df.end(), p[i]) - df.begin() + 1;
    }
    set<long long> cur;
    for (int i = N - 1; i >= 0; i--) {
      cur.insert(p[i]);
      if (*cur.begin() < p[i]) {
        auto mns = *prev(cur.lower_bound(p[i]));
        mn[p[i]] = max(mn[p[i]], mns);
        if (mn[p[i]] < p[i])
          need[mn[p[i]] - 1] =
              max(need[mn[p[i]] - 1], (long long)df.size() - p[i] + 1);
      }
    }
    long long res = INT_MAX;
    for (int i = df.size(); i >= 0; i--) {
      need[i] = max(need[i], need[i + 1]);
      res = min(res, i + need[i]);
    }
    cout << res << '\n';
  }
  return 0;
}
