#include <bits/stdc++.h>
using namespace std;
struct Val {
  long long val, i;
};
void solve() {
  long long n;
  cin >> n;
  Val a[n];
  for (Val& i : a) cin >> i.val;
  for (long long i = 0; i < n; i++) a[i].i = i;
  sort(a, a + n, [](Val a, Val b) { return a.val < b.val; });
  long long p = a[0].val;
  a[0].val = 1;
  for (long long i = 1; i < n; i++)
    if (p == a[i].val) {
      a[i].val = a[i - 1].val;
    } else {
      p = a[i].val;
      a[i].val = a[i - 1].val + 1;
    }
  sort(a, a + n, [](Val a, Val b) { return a.i < b.i; });
  bool first[n + 1];
  long long len[n + 1][3], last[n + 1];
  for (long long i = 0; i <= n; i++) first[i] = true;
  for (long long i = 0; i < n; i++) last[a[i].val] = i;
  for (long long i = 0; i <= n; i++)
    for (long long j = 0; j < 3; j++) len[i][j] = 0;
  for (long long i = 0; i < n; i++) {
    if (first[a[i].val]) {
      len[a[i].val][1] = len[a[i].val - 1][0];
      if (i > last[a[i].val - 1])
        len[a[i].val][1] = max(len[a[i].val][1], len[a[i].val - 1][1]);
    }
    first[a[i].val] = false;
    len[a[i].val][2] = max(len[a[i].val][2], len[a[i].val - 1][0]);
    if (i > last[a[i].val - 1])
      len[a[i].val][2] = max(len[a[i].val][2], len[a[i].val - 1][1]);
    for (long long j : {0, 1, 2}) len[a[i].val][j]++;
  }
  long long maxi = 0;
  for (long long i = 1; i <= n; i++)
    for (long long j = 0; j < 3; j++) maxi = max(maxi, len[i][j]);
  cout << n - maxi << '\n';
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t;
  cin >> t;
  while (t--) solve();
}
