#include <bits/stdc++.h>
#pragma optimize("O2")
using namespace std;
const int N = 2e5 + 3;
vector<int> pos[N];
int a[N], freq[N];
map<int, int> mp;
int find_greater(int x, int adj) {
  if (pos[adj].empty()) {
    return 0;
  }
  auto it =
      lower_bound(pos[adj].begin(), pos[adj].end(), x + 1) - pos[adj].begin();
  int ans = (int)pos[adj].size() - it;
  assert(ans >= 0);
  return ans;
}
int find_smaller(int x, int adj) {
  if (pos[adj].empty()) {
    return 0;
  }
  auto it = lower_bound(pos[adj].begin(), pos[adj].end(), x);
  return it - pos[adj].begin();
}
int ask_adjacent(int x) {
  int answer = 0;
  assert(x > 0);
  for (int i = 0; i < pos[x - 1].size(); ++i) {
    answer = max(answer, i + 1 + find_greater(pos[x - 1][i], x));
  }
  return answer;
}
int ask_arbitrary(int l, int r) {
  int Left = find_smaller(pos[l][0], l - 1);
  int Right = find_greater(pos[r].back(), r + 1);
  return Left + Right;
}
void solve() {
  int n;
  cin >> n;
  for (int i = 0; i <= n + 2; ++i) {
    freq[i] = 0;
    pos[i].clear();
  }
  mp.clear();
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    mp[a[i]];
  }
  int c = 1;
  for (auto &it : mp) {
    it.second = c++;
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    a[i] = mp[a[i]];
    pos[a[i]].push_back(i);
    ++freq[a[i]];
    ans = max(ans, freq[a[i]]);
  }
  vector<pair<int, int>> v;
  for (int i = 1; i <= n; ++i) {
    if (freq[i]) {
      v.push_back({i, freq[i]});
    }
  }
  vector<int> dp(v.size(), 1);
  for (int i = 1; i < v.size(); ++i) {
    assert(v[i].first == v[i - 1].first + 1);
    if (pos[v[i].first][0] > pos[v[i - 1].first].back()) {
      dp[i] += dp[i - 1];
      v[i].second += v[i - 1].second;
    }
    int st = ask_adjacent(v[i].first);
    ans = max(ans, st);
    if (dp[i] > 1) {
      int l = v[i].first - dp[i] + 1;
      int let = ask_arbitrary(l, v[i].first);
      ans = max(ans, let + v[i].second);
    }
  }
  cout << n - ans << '\n';
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
