#include <bits/stdc++.h>
using namespace std;
int main() {
  int t;
  cin >> t;
  for (; t; t--) {
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i].first;
      a[i].second = i;
    }
    vector<bool> used(n);
    sort(a.begin(), a.end());
    int cnt = 0;
    vector<vector<int>> v(n);
    vector<int> mp(n), addl(n), addr(n);
    for (int i = 0; i < n; i++) {
      if (i != 0 && a[i].first != a[i - 1].first) cnt++;
      v[cnt].push_back(a[i].second);
      mp[i] = cnt;
    }
    for (int i = 0; i <= cnt; i++) {
      if (i != 0) {
        int f = v[i][0];
        addl[i] =
            lower_bound(v[i - 1].begin(), v[i - 1].end(), f) - v[i - 1].begin();
      }
      if (i != cnt) {
        int f = v[i].back();
        addr[i] =
            v[i + 1].end() - lower_bound(v[i + 1].begin(), v[i + 1].end(), f);
      }
    }
    int ans = n - 1;
    int st = 0, fn = 0;
    while (fn < n) {
      fn++;
      while (fn < n && a[fn - 1].second < a[fn].second) {
        fn++;
      }
      int nans = fn - st + addl[mp[st]] + addr[mp[fn - 1]];
      ans = min(ans, n - nans);
      st = fn;
    }
    cout << ans << endl;
  }
}
