#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  while (N--) {
    int n;
    cin >> n;
    vector<long long> w;
    map<long long, long long> mi;
    for (int i = 0; i < n; i++) {
      long long t;
      cin >> t;
      w.push_back(t);
      mi[t] = 0;
    }
    int sz = 0;
    for (auto& it : mi) {
      it.second = sz;
      sz++;
    }
    vector<long long> pr(sz + 1, 0), pv(n);
    vector<pair<int, int> > ord, pad;
    vector<vector<long long> > ok;
    ok.assign(sz, vector<long long>());
    for (int i = 0; i < w.size(); i++) {
      w[i] = mi[w[i]];
      ok[w[i]].push_back(i);
      ord.push_back({w[i], i});
    }
    for (int i = 0; i < sz; i++) {
      pr[i + 1] = pr[i] + ok[i].size();
    }
    sort(ord.begin(), ord.end());
    for (int i = ord.size() - 1; i >= 0; i--) {
      int val = ord[i].first;
      int po = ord[i].second;
      if (val + 1 == sz) {
        pv[po] = 0;
      } else if (po < ok[val + 1][0]) {
        pv[po] = ok[val + 1].size() + pv[ok[val + 1].back()];
      } else {
        int ro = upper_bound(ok[val + 1].begin(), ok[val + 1].end(), po) -
                 ok[val + 1].begin();
        pv[po] = ok[val + 1].size() - ro;
      }
    }
    for (int i = 0; i < ord.size(); i++) {
      ord[i].second *= -1;
    }
    sort(ord.begin(), ord.end());
    long long res = n;
    for (int i = 0; i < ord.size(); i++) {
      int val = ord[i].first;
      int po = -ord[i].second;
      long long we = pv[po] + pr[val + 1];
      res = min(res, (n - we) + i);
    }
    cout << res << '\n';
  }
}
