#include <bits/stdc++.h>
using namespace std;
void setIO() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
  cout.tie(nullptr);
}
const int N = 2e5 + 5;
const int M = 2e3 + 5;
const long long inf = 9e17;
const long long mod = 1e9 + 7;
int xyz = 1;
int n;
int a[N];
int o[N];
int p[N];
int c[N];
int v[N];
int pr[N];
int dp[N];
bool cmp(int x, int y) { return a[x] < a[y]; }
void run() {
  cin >> n;
  for (int i = 1; i <= n; i++)
    cin >> a[i], o[i] = i, dp[i] = pr[i] = v[i] = p[i] = c[i] = 0;
  sort(o + 1, o + 1 + n, cmp);
  map<int, int> idx;
  int itr = 0;
  for (int i = 1; i <= n; i++)
    if (!idx[a[o[i]]]) idx[a[o[i]]] = ++itr;
  for (int i = 1; i <= n; i++) c[a[i] = idx[a[i]]]++;
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    dp[a[i]]++;
    dp[a[i]] =
        max(dp[a[i]],
            (v[a[i] - 1] == c[a[i] - 1] ? pr[a[i] - 1] : v[a[i] - 1]) + 1);
    ans = max(ans, dp[a[i]]);
    pr[a[i]] = v[a[i]] ? pr[a[i]] + 1 : dp[a[i]];
    ++v[a[i]];
  }
  cout << n - ans << "\n";
}
int main() {
  setIO();
  cin >> xyz;
  while (xyz--) run();
  return 0;
}
