#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
const vector<int> mods = {998244353, 1000000007, 1000000009};
const long long inf = 3e18;
const double pi = acos(-1.0);
const double eps = 0.0000001;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <class... K>
using umap = unordered_map<K...>;
template <class... K>
using uset = unordered_set<K...>;
const int N = 200100;
long long t, n, p, res;
vector<long long> a, b, pre_i, suf_i, dp;
umap<long long, long long> idx;
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout.precision(13);
  cin >> t;
  for (long long _t = (0); _t < (t); ++_t) {
    cin >> n;
    idx.clear();
    a.assign(n, 0);
    b.assign(n, 0);
    for (long long i = (0); i < (n); ++i) cin >> a[i];
    b = a;
    sort(begin(b), end(b));
    p = 1;
    for (long long i = (0); i < (n); ++i) {
      if ((idx.find(b[i]) != end(idx))) continue;
      idx[b[i]] = p++;
    }
    dp.assign(p + 10, 0);
    pre_i.assign(p + 10, 0);
    suf_i.assign(p + 10, 0);
    for (long long i = (0); i < (n); ++i) {
      a[i] = idx[a[i]];
      suf_i[a[i]]++;
    }
    res = 0;
    for (long long i = (0); i < (n); ++i) {
      res = max(res, pre_i[a[i] - 1] + suf_i[a[i]]);
      if (!pre_i[a[i]]) {
        if (suf_i[a[i] - 1])
          dp[a[i]] = pre_i[a[i] - 1];
        else
          dp[a[i]] = dp[a[i] - 1];
      }
      dp[a[i]]++;
      pre_i[a[i]]++;
      suf_i[a[i]]--;
      if (!suf_i[a[i]]) res = max(res, dp[a[i]] + suf_i[a[i] + 1]);
      res = max(res, pre_i[a[i]] + suf_i[a[i] + 1]);
    }
    cout << n - res << "\n";
  }
  return 0;
}
