#include <bits/stdc++.h>
#pragma GCC optimize(3, "Ofast", "inline")
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const long long maxn = (long long)2e5 + 5;
const long long mod = 998244353;
const long long inf = 0x3f3f3f3f;
long long T = 1;
long long a[maxn], b[maxn];
long long dp[maxn][3];
long long l[maxn], r[maxn];
long long pos[maxn], num[maxn];
void solve() {
  long long n;
  cin >> n;
  for (long long i = 1; i <= n; ++i)
    cin >> a[i], b[i] = a[i], dp[i][0] = dp[i][1] = dp[i][2] = 0,
                 l[i] = r[i] = 0, num[i] = 0;
  sort(b + 1, b + n + 1);
  long long tot = unique(b + 1, b + n + 1) - (b + 1);
  for (long long i = 1; i <= n; ++i) {
    a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
    r[a[i]] = i;
    if (!l[a[i]]) l[a[i]] = i, pos[a[i]] = i;
    ++num[a[i]];
  }
  long long maxx = 1;
  for (long long i = 1; i <= n; ++i) {
    dp[i][0] = dp[pos[a[i]]][0] + 1;
    dp[i][1] = max(dp[pos[a[i]]][1] + 1,
                   max(dp[pos[a[i] - 1]][0] + 1, dp[pos[a[i] - 1]][2] + 1));
    if (i == r[a[i]]) dp[i][2] = dp[l[a[i]]][1] + num[a[i]] - 1;
    pos[a[i]] = i;
    for (long long j = 0; j <= 2; ++j) maxx = max(maxx, dp[i][j]);
  }
  cout << n - maxx << '\n';
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> T;
  while (T--) solve();
  return 0;
}
