#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int N = 2e5 + 1;
const int M = 1e6 + 1;
const int INF = 1e9 + 7;
const int MOD[2] = {998244353, int(1e9) + 7};
const int X[4] = {1, -1, 0, 0};
const int Y[4] = {0, 0, 1, -1};
const double long PI = 3.14159265358979323846;
mt19937 gen(19937);
int a[N], b[N], ans = 0;
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T;
  cin >> T;
  while (T--) {
    int n;
    ans = 0;
    cin >> n;
    vector<int> u[n];
    vector<pair<int, int> > pref(n, {0, 0}), suf(n, {0, 0});
    for (int i(0); i < n; ++i) {
      cin >> a[i];
      b[i] = a[i];
    }
    sort(a, a + n);
    int m = 0;
    for (int i(1); i < n; ++i) {
      if (a[i] == a[m]) continue;
      a[++m] = a[i];
    }
    ++m;
    map<int, int> mp;
    for (int i(0); i < n; ++i) {
      if (!mp.count(a[i])) {
        mp[a[i]] = i;
      }
    }
    for (int i(0); i < n; ++i) {
      a[i] = mp[b[i]];
      u[a[i]].push_back(i);
    }
    for (int i(0); i < m; ++i) {
      if (i) {
        if (u[i - 1].back() < u[i][0]) {
          pref[i].first = 1;
          pref[i].second = u[i - 1].size();
        } else {
          pref[i].first = 0;
          pref[i].second = 0;
          for (int j(0); j < u[i - 1].size(); ++j) {
            if (u[i][0] > u[i - 1][j]) {
              pref[i].second = j + 1;
            }
          }
        }
      }
      if (m - 1 != i) {
        if (u[i + 1][0] > u[i].back()) {
          suf[i].first = 1;
          suf[i].second = u[i + 1].size();
        } else {
          suf[i].first = 0;
          for (int j(int(u[i + 1].size()) - 1); j >= 0; --j) {
            if (u[i].back() < u[i + 1][j]) {
              suf[i].second = int(u[i + 1].size()) - j;
            }
          }
          for (int j(0); j < u[i].size(); ++j) {
            if (u[i][j] > u[i + 1].back()) {
              ans = max(ans, j + 1);
            } else {
              int l =
                  int(upper_bound(u[i + 1].begin(), u[i + 1].end(), u[i][j]) -
                      u[i + 1].begin());
              ans = max(ans, j + 1 + int(u[i + 1].size()) - l);
            }
          }
        }
      }
    }
    for (int i(0); i < m; ++i) {
      int now = 0;
      now += pref[i].second;
      now += u[i].size();
      int j = i;
      while (j + 1 < m && suf[j].first == 1) {
        now += suf[j].second;
        ++j;
      }
      now += suf[j].second;
      i = j;
      ans = max(ans, now);
    }
    cout << n - ans << '\n';
  }
  return 0;
}
