#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int inf = 1000 * 1000 * 1000;
const int mod = 998244353;
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
int t;
int n;
int a[N];
multiset<int> q;
multiset<int>::iterator it;
map<int, int> mp;
int dp[N];
int sum[N];
int main() {
  cin >> t;
  vector<int> answ;
  while (t--) {
    cin >> n;
    vector<int> all;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      all.push_back(a[i]);
    }
    sort(all.begin(), all.end());
    all.resize(unique(all.begin(), all.end()) - all.begin());
    int mx = 0;
    for (int i = 1; i <= n; i++) {
      dp[i] = 1;
      sum[i] = 1;
      int ind = lower_bound(all.begin(), all.end(), a[i]) - all.begin();
      bool lava = false;
      if (mp.find(a[i]) != mp.end()) {
        dp[i] = max(dp[i], 1 + dp[mp[a[i]]]);
        sum[i] += sum[mp[a[i]]];
        lava = true;
      }
      if (ind != 0 && mp.find(all[ind - 1]) != mp.end()) {
        dp[i] = max(dp[i], 1 + sum[mp[all[ind - 1]]]);
        if (!lava) sum[i] += sum[mp[all[ind - 1]]];
      }
      mx = max(mx, dp[i]);
      mx = max(mx, sum[i]);
      mp[a[i]] = i;
    }
    printf("%d\n", n - mx);
    mp.clear();
  }
  return 0;
}
