#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
  while (b) {
    int c = a % b;
    a = b;
    b = c;
  }
  return a;
}
int main() {
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout.setf(ios::fixed);
  cout.precision(20);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
      cin >> v[i];
    }
    map<int, vector<int>> mp;
    for (int i = 0; i < n; ++i) {
      mp[v[i]].push_back(i);
    }
    int m = mp.size();
    vector<pair<int, vector<int>>> vv(m);
    auto it = mp.begin();
    for (int i = 0; i < m; ++i) {
      vv[i].first = it->first;
      vv[i].second = move(it->second);
      ++it;
    }
    vector<int> from_right(m);
    from_right[m - 1] = vv[m - 1].second.size();
    for (int i = m - 2; i >= 0; --i) {
      from_right[i] = vv[i].second.size();
      auto& nv = vv[i + 1].second;
      auto jt = upper_bound(nv.begin(), nv.end(), vv[i].second.back());
      if (jt == nv.begin()) {
        from_right[i] += from_right[i + 1];
      } else {
        from_right[i] += nv.end() - jt;
      }
    }
    vector<int> from_left(m);
    from_left[0] = 0;
    for (int i = 1; i < m; ++i) {
      auto& pv = vv[i - 1].second;
      from_left[i] =
          lower_bound(pv.begin(), pv.end(), vv[i].second.front()) - pv.begin();
    }
    int mxc = 1;
    for (int i = 0; i < m; ++i) {
      mxc = max(mxc, from_left[i] + from_right[i]);
    }
    for (int i = 1; i < m; ++i) {
      auto& pv = vv[i - 1].second;
      auto& nv = vv[i].second;
      for (int pp = 0; pp < (int)pv.size(); ++pp) {
        int np = lower_bound(nv.begin(), nv.end(), pv[pp]) - nv.begin();
        mxc = max(mxc, 1 + pp + (int)nv.size() - np);
      }
    }
    cout << n - mxc << endl;
  }
  return 0;
}
