#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int mod = 998244353;
int f[N][3];
vector<int> num;
int l[N], r[N], cnt[N], pos[N];
int a[N];
int main() {
  ios::sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int i;
    num.clear();
    for (i = 1; i <= n; i++) {
      cin >> a[i];
      num.push_back(a[i]);
      f[i][0] = f[i][1] = f[i][2] = 0;
      l[i] = cnt[i] = r[i] = 0;
    }
    sort(num.begin(), num.end());
    num.erase(unique(num.begin(), num.end()), num.end());
    for (i = 1; i <= n; i++) {
      int d = lower_bound(num.begin(), num.end(), a[i]) - num.begin() + 1;
      r[d] = i;
      if (!l[d]) {
        l[d] = i;
        pos[d] = i;
      }
      cnt[d]++;
    }
    int ans = 1;
    for (i = 1; i <= n; i++) {
      int d = lower_bound(num.begin(), num.end(), a[i]) - num.begin() + 1;
      f[i][0] = f[pos[d]][0] + 1;
      f[i][1] = max(f[pos[d]][1] + 1,
                    max(f[pos[d - 1]][0] + 1, f[pos[d - 1]][2] + 1));
      if (i == r[d]) {
        f[i][2] = f[l[d]][1] + cnt[d] - 1;
      }
      pos[d] = i;
      for (int j = 0; j < 3; j++) {
        ans = max(ans, f[i][j]);
      }
    }
    cout << n - ans << endl;
  }
  return 0;
}
