#include <bits/stdc++.h>
using namespace std;
void shikhar7s(long long int cas) {
  long long int n, i;
  cin >> n;
  long long int a[n], vs;
  map<long long int, long long int> m;
  vector<long long int> v;
  for (i = 0; i < n; i++) {
    cin >> a[i];
    if (!m.count(a[i])) v.push_back(a[i]);
    m[a[i]] = 1;
  }
  sort(v.begin(), v.end());
  vs = (long long int)v.size();
  for (i = 0; i < vs; i++) {
    m[v[i]] = i;
  }
  vector<long long int> s[vs + 5];
  long long int ans = 0;
  for (i = 0; i < n; i++) {
    s[m[a[i]]].push_back(i);
    ans = max(ans, (long long int)s[m[a[i]]].size());
  }
  long long int j, ss, c = 0, k;
  for (i = 0; i < vs; i++) {
    ss = (long long int)s[i].size();
    c += ss;
    ans = max(ans, c);
    if (i < vs - 1 && s[i][ss - 1] > s[i + 1][0]) {
      j = upper_bound(s[i + 1].begin(), s[i + 1].end(), s[i][ss - 1]) -
          s[i + 1].begin();
      ss = (long long int)s[i + 1].size();
      ans = max(ans, c + ss - j);
      ss = (long long int)s[i].size();
      for (k = ss - 1; k >= 0; k--) {
        j = upper_bound(s[i + 1].begin(), s[i + 1].end(), s[i][k]) -
            s[i + 1].begin();
        ans = max(ans, k + 1 + (long long int)s[i + 1].size() - j);
      }
      j = upper_bound(s[i].begin(), s[i].end(), s[i + 1][0]) - s[i].begin();
      j--;
      c = j + 1;
    }
  }
  ans = max(ans, c);
  cout << n - ans << "\n";
}
signed main() {
  std::ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  long long int t = 1;
  cin >> t;
  long long int cas = 1;
  while (cas <= t) {
    shikhar7s(cas);
    cas++;
  }
  return 0;
}
