#include <bits/stdc++.h>
using namespace std;
int32_t main() {
  int T;
  cin >> T;
  while (T--) {
    int n, k, ans = 0;
    cin >> n;
    vector<int> arr(n);
    map<int, vector<int>> codes;
    for (int i = 0; i < n; ++i) {
      cin >> arr[i];
      codes[arr[i]].push_back(i);
    }
    int code = 0;
    for (auto it : codes) {
      for (auto ut : it.second) {
        arr[ut] = code;
      }
      code++;
    }
    vector<int> last(code), first(code), dp2(code, 0), count(code, 0),
        curcount(code, 0);
    vector<vector<int>> indices(code, vector<int>());
    for (int i = 0; i < n; ++i) {
      last[arr[i]] = i;
      count[arr[i]]++;
      indices[arr[i]].push_back(i);
    }
    for (int i = n - 1; i >= 0; --i) first[arr[i]] = i;
    dp2[0] = count[0];
    for (int i = 1; i < code; ++i) {
      if (last[i - 1] < first[i]) {
        dp2[i] = count[i] + dp2[i - 1];
      } else {
        dp2[i] = count[i] +
                 lower_bound(indices[i - 1].begin(), indices[i - 1].end(),
                             first[i]) -
                 indices[i - 1].begin();
      }
    }
    for (int i = n - 1; i >= 0; --i) {
      if (i == last[arr[i]] && arr[i] < code - 1) {
        dp2[arr[i]] += curcount[arr[i] + 1];
      }
      curcount[arr[i]]++;
    }
    for (int i = 0; i < code; ++i) ans = max(ans, dp2[i]);
    for (int i = 0; i < n; ++i) {
      ans = max(ans,
                (int)((arr[i] > 0 ? (lower_bound(indices[arr[i] - 1].begin(),
                                                 indices[arr[i] - 1].end(), i) -
                                     indices[arr[i] - 1].begin())
                                  : 0) +
                      (indices[arr[i]].end() -
                       lower_bound(indices[arr[i]].begin(),
                                   indices[arr[i]].end(), i))));
    }
    cout << n - ans << endl;
  }
  return 0;
}
