#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
pair<int, int> b[maxn];
int cnt;
vector<int> c[maxn];
int num[maxn];
int ans = -1;
int T, n;
int main() {
  cin >> T;
  while (T--) {
    for (int i = 1; i <= 200000; i++) c[i].clear();
    ans = -1;
    memset(num, 0, sizeof(num));
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i], b[i].first = a[i], b[i].second = i;
    sort(b, b + n);
    cnt = 1;
    for (int i = 0; i < n; i++) {
      if (i && b[i].first != b[i - 1].first) {
        cnt++;
      }
      a[b[i].second] = cnt;
      c[cnt].push_back(b[i].second);
      num[cnt]++;
    }
    for (int i = 1; i <= cnt; i++) {
      int sum = num[i];
      int r = i;
      for (int j = i + 1; j <= cnt; j++) {
        if (c[j][0] >= c[j - 1][num[j - 1] - 1]) {
          r = j;
          sum += num[j];
        } else {
          break;
        }
      }
      if (i > 1) {
        sum += lower_bound(c[i - 1].begin(), c[i - 1].end(), c[i][0]) -
               c[i - 1].begin();
      }
      if (r < cnt) {
        sum += num[r + 1];
        sum -= lower_bound(c[r + 1].begin(), c[r + 1].end(), c[r][num[r] - 1]) -
               c[r + 1].begin();
      }
      i = r;
      ans = max(ans, sum);
    }
    for (int i = 1; i < cnt + 1; i++) {
      ans = max(ans, num[i]);
    }
    for (int i = 1; i < cnt; i++) {
      for (int j = 0; j < num[i]; j++) {
        int sum = j + 1 + num[i + 1];
        sum -= lower_bound(c[i + 1].begin(), c[i + 1].end(), c[i][j]) -
               c[i + 1].begin();
        ans = max(ans, sum);
      }
    }
    cout << n - ans << "\n";
  }
  return 0;
}
