#include <bits/stdc++.h>
using namespace std;
vector<int> nxtLower;
vector<int> prevLower;
vector<int> prevSame;
int getdp(vector<vector<int> > &mem, int i, int state) {
  int &res = mem[i][state];
  if (res != -1) {
    return res;
  }
  if (prevSame[i] == -1) {
    res = 1;
  } else {
    res = getdp(mem, prevSame[i], state) + 1;
  }
  if (prevLower[i] != -1) {
    int source = nxtLower[i] != -1 ? 0 : 1;
    if (prevSame[i] == -1)
      if (state >= 1)
        res = max(res, getdp(mem, prevLower[i], source) + 1);
      else if (state == 2)
        res = max(res, getdp(mem, prevLower[i], source) + 1);
  }
  if (state > 0) res = max(res, getdp(mem, i, state - 1));
  return res;
}
void go() {
  int n;
  cin >> n;
  vector<int> v;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    v.push_back(a);
  }
  vector<int> s = v;
  sort(s.begin(), s.end());
  s.erase(unique(s.begin(), s.end()), s.end());
  for (int &a : v) {
    a = lower_bound(s.begin(), s.end(), a) - s.begin();
  }
  nxtLower = vector<int>(n);
  prevLower = vector<int>(n);
  prevSame = vector<int>(n);
  map<int, int> prev;
  for (int i = 0; i < v.size(); ++i) {
    int a = v[i];
    prevLower[i] = prev.count(a - 1) ? prev[a - 1] : -1;
    prevSame[i] = prev.count(a) ? prev[a] : -1;
    prev[a] = i;
  }
  prev.clear();
  for (int i = v.size() - 1; i >= 0; --i) {
    int a = v[i];
    nxtLower[i] = prev.count(a - 1) ? prev[a - 1] : -1;
    prev[a] = i;
  }
  vector<vector<int> > dp(n, vector<int>(3, -1));
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    ans = max(ans, getdp(dp, i, 2));
  }
  cout << n - ans << endl;
}
int main() {
  int testn;
  cin >> testn;
  for (int testi = 0; testi < testn; testi++) {
    go();
  }
}
