#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const long long linf = 0x3f3f3f3f3f3f3f3f;
int a[200100];
bool cmp(pair<int, int> a, pair<int, int> b) {
  if (a.first == b.first) return a.second > b.second;
  return a.first < b.first;
}
int main() {
  int t_;
  scanf("%d", &t_);
  while (t_--) {
    int n;
    scanf("%d", &n);
    vector<int> v(n);
    map<int, int> m;
    for (int i = 0; i < n; i++) {
      scanf("%d", &a[i]);
      v[i] = a[i];
    }
    sort(v.begin(), v.end());
    int xx = 0;
    for (int i = 0; i < n; i++) {
      if (m.find(v[i]) == m.end()) {
        m[v[i]] = xx;
        xx++;
      }
    }
    for (int i = 0; i < n; i++) a[i] = m[a[i]];
    vector<pair<int, int> > p, q;
    for (int i = 0; i < n; i++) {
      p.push_back({a[i], i});
      q.push_back({a[i], i});
    }
    sort(p.begin(), p.end());
    sort(q.begin(), q.end(), cmp);
    int l = 0, r = 0;
    int last = -1;
    int cnt = 1;
    int ans = 1;
    while (l < n - 1) {
      while (l < n - 1 && p[l].first == last) l++, cnt--;
      while (l > r) r++, cnt++;
      while (r < n - 1 && p[r].second < p[r + 1].second) r++, cnt++;
      last = p[l].first;
      int aux = 0;
      int x = l - 1, y = r + 1;
      while (x >= 0 && q[x].second < p[l].second &&
             q[x].first == p[l].first - 1)
        x--, aux++;
      while (y < n && q[y].second > p[r].second && q[y].first == p[r].first + 1)
        y++, aux++;
      ans = max(ans, cnt + aux);
    }
    for (int i = 1; i < n; i++) {
      if (q[i].first != q[i - 1].first) {
        int x = i;
        int y = i;
        int cnt = 1;
        while (x > 0 && q[x - 1].first == q[i].first - 1 &&
               q[x - 1].second < q[y].second)
          x--, cnt++;
        ans = max(ans, cnt);
        while (y < n && q[y].first == q[i].first) {
          while (q[x].first == q[i].first - 1 && q[x].second > q[y].second)
            x++, cnt--;
          ans = max(ans, cnt);
          y++, cnt++;
        }
      }
    }
    printf("%d\n", n - ans);
  }
  return 0;
}
