#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
int t;
int n;
pair<int, int> a[N];
int main() {
  ios_base::sync_with_stdio(false);
  cout.tie(0);
  cin.tie(0);
  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = 0; i < n; ++i) {
      cin >> a[i].first;
      a[i].second = -i;
    }
    sort(a, a + n);
    int cnt = 1, ans = n - 1;
    int j = 0;
    set<pair<int, int>> s;
    a[0].second = -a[0].second;
    s.insert({a[0].first, a[0].second});
    for (int i = 1; i < n; ++i) {
      a[i].second = -a[i].second;
      auto it = s.lower_bound(a[i]);
      while (j < i && (it != s.end() && a[i].second > it->second ||
                       it != s.begin() && a[i].second < prev(it)->second)) {
        s.erase(a[j++]);
        it = s.lower_bound(a[i]);
      }
      s.insert(a[i]);
      ans = min(ans, n - i + j - 1);
    }
    cout << ans << '\n';
  }
}
