#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    vector<int> arr(n);
    vector<pair<int, int>> vpr(n);
    for (long long i = 0; i <= n - 1; i++) {
      cin >> arr[i];
      vpr[i] = {arr[i], i};
    }
    sort(vpr.begin(), vpr.end());
    int j = 0;
    vector<int> trfs(n);
    unordered_multiset<int> mst;
    for (int i = 0; i < n; ++i) {
      if (i > 0 && vpr[i].first != vpr[i - 1].first) {
        j++;
      }
      trfs[vpr[i].second] = j;
      mst.insert(j);
    }
    vector<int> dp1(n, 1), dp2(n), dp3(n);
    unordered_map<int, int> pos;
    for (int i = 0; i < n; ++i) {
      if (mst.count(trfs[i])) mst.erase(mst.find(trfs[i]));
      if (pos.count(trfs[i] - 1)) {
        if (!pos.count(trfs[i])) {
          dp2[i] = dp1[pos[trfs[i] - 1]] + 1;
          if (!mst.count(trfs[i] - 1)) {
            dp2[i] = max(dp2[i], dp2[pos[trfs[i] - 1]] + 1);
          }
        }
        if (!mst.count(trfs[i] - 1)) {
          dp3[i] = dp2[pos[trfs[i] - 1]] + 1;
        }
        dp3[i] = max(dp3[i], dp1[pos[trfs[i] - 1]] + 1);
      }
      if (pos.count(trfs[i])) {
        dp1[i] = dp1[pos[trfs[i]]] + 1;
        dp3[i] = max(dp3[i], dp3[pos[trfs[i]]] + 1);
        dp2[i] = max(dp2[i], dp2[pos[trfs[i]]] + 1);
      }
      dp2[i] = max(dp2[i], dp1[i]);
      dp3[i] = max(dp3[i], dp2[i]);
      pos[trfs[i]] = i;
    }
    cout << n - *max_element(dp3.begin(), dp3.end()) << "\n";
  }
  return 0;
}
