#include <bits/stdc++.h>
using namespace std;
const long long N = 3e5 + 5, inf = 1e18, mod = 998244353;
const double PI = 3.1415926536;
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool is_prime(long long n) {
  for (long long i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}
vector<long long> fact(long long n) {
  n = abs(n);
  long long t = 0;
  vector<long long> ans;
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ans.push_back(i);
      if (n / i != i) {
        ans.push_back(n / i);
      }
    }
  }
  return ans;
}
inline long long getPow(long long a, long long b) {
  long long res = 1ll, tp = a;
  while (b) {
    if (b & 1ll) {
      res *= tp;
    }
    tp *= tp;
    b >>= 1ll;
  }
  return res;
}
long long vec_mult(const pair<long long, long long>& t1,
                   const pair<long long, long long>& t2,
                   const pair<long long, long long>& t3) {
  const long long &x1 = t1.first, y1 = t1.second;
  const long long &x2 = t2.first, y2 = t2.second;
  const long long &x3 = t3.first, y3 = t3.second;
  return abs((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1));
}
void ok() {
  cout << "YES" << endl;
  exit(0);
}
void no() {
  cout << "NO" << endl;
  exit(0);
}
inline long long nxt() {
  long long x;
  cin >> x;
  return x;
}
void compress(vector<int>& a) {
  vector<int> buf = a;
  sort((buf).begin(), (buf).end());
  (buf).resize(unique((buf).begin(), (buf).end()) - (buf).begin());
  for (int i = 0; i < a.size(); i++) {
    a[i] = 1 + (lower_bound(buf.begin(), buf.end(), a[i]) - buf.begin());
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int q = nxt();
  while (q--) {
    int n = nxt();
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      a[i] = nxt();
    }
    compress(a);
    map<int, vector<int>> mp;
    vector<int> l(n + 1, mod);
    vector<int> r(n + 1, -mod);
    int mx = 0;
    for (int i = 0; i < n; i++) {
      l[a[i]] = min(l[a[i]], i);
      r[a[i]] = max(r[a[i]], i);
      mp[a[i]].push_back(i);
      mx = max(mx, a[i]);
    }
    vector<int> dp(mx + 1);
    int ans = 0;
    for (int i = 1; i <= mx; i++) {
      dp[i] = mp[i].size();
      if (l[i] > r[i - 1]) {
        dp[i] = dp[i - 1] + mp[i].size();
      }
      int tmp = 0;
      for (const auto& ind : mp[i - 1]) {
        if (ind < l[i]) {
          tmp++;
        }
      }
      dp[i] = max(dp[i], tmp + (int)mp[i].size());
      tmp = 0;
      for (const auto& ind : mp[i]) {
        if (ind > r[i - 1]) {
          tmp++;
        }
      }
      ans = max({ans, dp[i - 1] + tmp, dp[i]});
      vector<pair<int, int>> arr;
      for (const auto& x : mp[i - 1]) {
        arr.push_back({x, 0});
      }
      for (const auto& x : mp[i]) {
        arr.push_back({x, 1});
      }
      sort(arr.begin(), arr.end());
      int dp0 = 0, dp1 = 0;
      for (const auto& x : arr) {
        if (!x.second) {
          dp0++;
          dp1 = max(dp1, dp0);
        } else {
          dp1++;
        }
      }
      ans = max(ans, dp1);
    }
    cout << n - ans << '\n';
  }
  return 0;
}
