#include <bits/stdc++.h>
using namespace std;
template <typename T>
istream& operator>>(istream& is, vector<T>& a) {
  for (T& ai : a) is >> ai;
  return is;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> const& a) {
  os << "[ ";
  for (const T& ai : a) os << ai << " ";
  return os << "]";
}
template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& a) {
  return is >> a.first >> a.second;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2> const& a) {
  return os << "(" << a.first << ", " << a.second << ")";
}
int f() {
  int n;
  cin >> n;
  vector<int> a(n);
  cin >> a;
  vector<int> val(a);
  sort((val).begin(), (val).end());
  int m = unique((val).begin(), (val).end()) - val.begin();
  val.resize(m);
  map<int, int> idx;
  for (int i = 0; i < m; ++i) idx[val[i]] = i;
  vector<vector<int> > tiers(m);
  for (int i = 0; i < n; ++i) tiers[idx[a[i]]].push_back(i);
  int i = 0, j = 1, r = 0;
  while (i < m) {
    while (j < m && tiers[j - 1].back() < tiers[j].front()) ++j;
    int s = 0, lb = tiers[i].front(), ub = tiers[j - 1].back();
    for (int k = i; k < j; ++k) s += tiers[k].size();
    if (i - 1 >= 0) {
      for (int x : tiers[i - 1]) {
        if (x < lb) ++s;
      }
    }
    if (j < m) {
      for (int x : tiers[j]) {
        if (x > ub) ++s;
      }
    }
    r = max(r, s);
    i = j++;
  }
  for (int i = 0; i < m - 1; ++i) {
    int j = 0, jz = tiers[i + 1].size();
    int s = jz;
    for (int lhs : tiers[i]) {
      ++s;
      while (j < jz && tiers[i + 1][j] <= lhs) {
        ++j;
        --s;
      }
      r = max(r, s);
    }
  }
  return n - r;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) cout << f() << "\n";
  return 0;
}
