#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  vector<pair<int, int>> val;
  {
    vector<pair<int, int>> ra(n);
    for (int i = 0; i < n; ++i) {
      cin >> ra[i].first;
      ra[i].second = i;
    }
    sort(ra.begin(), ra.end());
    for (int i = 0; i < n; ++i) {
      a[i] = ra[i].second;
      if (i == 0 || ra[i].first != ra[i - 1].first)
        val.push_back({i, i});
      else
        ++val.back().second;
    }
  }
  int nbVal = val.size();
  int res = 0;
  int cur = 0;
  for (int iVal = 0; iVal < nbVal; ++iVal) {
    int beg = val[iVal].first;
    if (iVal > 0 && a[beg] < a[beg - 1]) {
      cur = 0;
      for (int x = val[iVal - 1].first; x <= val[iVal - 1].second; ++x) {
        if (a[x] < a[beg]) ++cur;
      }
    }
    cur += val[iVal].second - beg + 1;
    int sub = cur;
    if (iVal + 1 < nbVal) {
      for (int x = val[iVal + 1].first; x <= val[iVal + 1].second; ++x) {
        if (a[x] > a[val[iVal].second]) ++sub;
      }
    }
    res = max(res, sub);
  }
  for (int iVal = 0; iVal < nbVal - 1; ++iVal) {
    int ptr = val[iVal + 1].first;
    int sub = val[iVal + 1].second - ptr + 1;
    for (int x = val[iVal].first; x <= val[iVal].second; ++x) {
      ++sub;
      while (ptr <= val[iVal + 1].second && a[x] > a[ptr]) {
        ++ptr;
        --sub;
      }
      res = max(res, sub);
    }
  }
  cout << n - res << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int nbTests;
  cin >> nbTests;
  for (int iTest = 0; iTest < nbTests; ++iTest) {
    solve();
  }
}
