#include <bits/stdc++.h>
int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  int t;
  std::cin >> t;
  while (t--) {
    int n;
    std::cin >> n;
    std::vector<int> v(n);
    for (int& x : v) std::cin >> x;
    std::vector<int> vals = v;
    std::sort(vals.begin(), vals.end());
    vals.erase(std::unique(vals.begin(), vals.end()), vals.end());
    int m = vals.size();
    for (int& x : v)
      x = std::lower_bound(vals.begin(), vals.end(), x) - vals.begin();
    std::vector<std::vector<int>> occ(m);
    std::vector<int> last(m, -1), first(m, -1);
    for (int i = 0; i < n; ++i) {
      occ[v[i]].push_back(i);
      last[v[i]] = i;
      if (first[v[i]] == -1) first[v[i]] = i;
    }
    std::vector<int> su(m);
    std::iota(su.begin(), su.end(), 0);
    for (int i = m - 2; i >= 0; --i)
      if (last[i] < first[i + 1]) su[i] = su[i + 1];
    std::vector<int> sum_a(m);
    std::vector<int> sum_b(m);
    for (int i = m - 2; i >= 0; --i) {
      int k = first[i + 1];
      for (int u : occ[i]) sum_a[i] += u < k;
    }
    for (int i = 1; i < m; ++i) {
      int k = last[i - 1];
      for (int u : occ[i]) sum_b[i] += u > k;
    }
    std::vector<int> pre_sums(m + 1);
    for (int i = 0; i < m; ++i)
      pre_sums[i + 1] = pre_sums[i] + (int)occ[i].size();
    int r = 0;
    for (int i = 0; i < m; ++i) {
      int j = su[i];
      int off = pre_sums[j + 1] - pre_sums[i];
      off += i - 1 >= 0 ? sum_a[i - 1] : 0;
      off += j + 1 < n ? sum_b[j + 1] : 0;
      r = std::max(r, off);
    }
    std::cout << n - r << '\n';
  }
}
