#include <bits/stdc++.h>
using namespace std;
class A {
 public:
  void solve() {
    int t;
    cin >> t;
    while (t--) {
      int x, y;
      cin >> x >> y;
      string s;
      cin >> s;
      int u = 0, d = 0, r = 0, l = 0;
      for (char c : s) {
        if (c == 'U') u++;
        if (c == 'D') d++;
        if (c == 'R') r++;
        if (c == 'L') l++;
      }
      bool ok = true;
      if (x >= 0) {
        if (r < x) ok = false;
      } else if (abs(l) < abs(x))
        ok = false;
      if (y >= 0) {
        if (u < y) ok = false;
      } else if (abs(d) < abs(y))
        ok = false;
      if (ok)
        cout << "YES" << endl;
      else
        cout << "NO" << endl;
    }
  }
};
class B {
 public:
  void solve() {
    int t;
    cin >> t;
    while (t--) {
      long long n, k;
      cin >> n >> k;
      vector<long long> h(n + 1);
      for (int i = 1; i <= n; i++) cin >> h[i];
      int res = 0;
      while (k) {
        bool change = false;
        res = 1;
        for (int i = 1; i < n; i++) {
          if (h[i] >= h[i + 1])
            res = i + 1;
          else {
            h[i]++;
            res = i;
            k--;
            change = true;
            break;
          }
        }
        if (!change) break;
      }
      if (res == n)
        cout << -1 << endl;
      else
        cout << res << endl;
    }
  }
};
class C {
 public:
  void solve() {
    int t;
    cin >> t;
    while (t--) {
      int n, m;
      cin >> n >> m;
      vector<int> res(m + 1, 0), a(n + 1), b(n + 1), c(m + 1);
      vector<int> matched(n + 1, 0);
      unordered_map<int, vector<int>> umc;
      for (int i = 1; i <= n; i++) cin >> a[i];
      for (int i = 1; i <= n; i++) {
        cin >> b[i];
        if (a[i] == b[i])
          matched[a[i]] = i;
        else
          umc[b[i]].push_back(i);
      }
      for (int i = 1; i <= m; i++) cin >> c[i];
      vector<int> np;
      for (int i = 1; i <= m; i++) {
        if (!umc[c[i]].empty()) {
          res[i] = umc[c[i]].back();
          matched[c[i]] = res[i];
          umc[c[i]].pop_back();
        } else {
          if (matched[c[i]] != 0) res[i] = matched[c[i]];
        }
        if (res[i] == 0)
          np.push_back(i);
        else {
          while (!np.empty()) {
            res[np.back()] = res[i];
            np.pop_back();
          }
        }
      }
      int cnt = 0;
      for (auto it : umc) cnt += umc[it.first].size();
      if (!np.empty() || cnt != 0)
        cout << "NO" << endl;
      else {
        cout << "YES" << endl;
        for (int i = 1; i <= m; i++) cout << res[i] << " ";
        cout << endl;
      }
    }
  }
};
class D {
 public:
  void solve() {
    int t;
    cin >> t;
    while (t--) {
      int n, m;
      cin >> n >> m;
      vector<string> g(n);
      vector<int> a(3, -1);
      vector<vector<vector<int>>> cnt(n, vector<vector<int>>(2));
      for (int i = 0; i < n; i++) cin >> g[i];
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          if (j == i) continue;
          if (cnt[i][g[i][j] - 'a'].size() < 2)
            cnt[i][g[i][j] - 'a'].push_back(j);
          if (g[i][j] == g[j][i]) {
            a[0] = i;
            a[1] = j;
          }
        }
      }
      if (a[0] != -1 && a[1] != -1) {
        cout << "YES" << endl;
        for (int i = 0; i <= m; i++) {
          cout << a[i % 2] + 1 << ' ';
        }
        cout << endl;
        continue;
      }
      if (m % 2 == 0) {
        bool select = (m / 2) % 2 == 0 ? 1 : 0;
        for (int i = 0; i < n; i++) {
          for (int k = 0; k < 2; k++) {
            for (int p : cnt[i][k]) {
              int next = select ? i : p;
              int flag = select ? 1 - k : k;
              for (int q : cnt[next][flag]) {
                if (p == q) continue;
                cout << "YES" << endl;
                a[0] = i + 1;
                a[1] = p + 1;
                a[2] = q + 1;
                for (int r = 0; r <= m / 2; r++) {
                  cout << a[r % 2] << " ";
                }
                if (select) {
                  a[1] = a[2];
                } else {
                  a[0] = a[1];
                  a[1] = a[2];
                }
                for (int r = m / 2 + 1, cur = 1; r <= m; r++, cur ^= 1) {
                  cout << a[cur] << " ";
                }
                goto GG;
              }
            }
          }
        }
        cout << "NO";
      GG:
        cout << endl;
      } else {
        cout << "YES" << endl;
        for (int i = 0; i <= m; i++) {
          cout << i % 2 + 1 << ' ';
        }
      }
    }
  }
};
class E {
 public:
  int solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int maxn = 5e5 + 10;
    vector<int> cnt(maxn, 0);
    vector<int> l(maxn), r(maxn);
    vector<int> dp(n + 10, 0);
    for (int i = 1; i <= n; i++) {
      r[a[i]] = i;
    }
    for (int i = n; i >= 1; i--) {
      l[a[i]] = i;
    }
    dp[n] = 1;
    cnt[a[n]]++;
    for (int i = n - 1; i >= 1; i--) {
      cnt[a[i]]++;
      if (i == l[a[i]]) {
        dp[i] = max(dp[i], cnt[a[i]] + dp[r[a[i]] + 1]);
      }
      dp[i] = max(dp[i], cnt[a[i]]);
      dp[i] = max(dp[i], dp[i + 1]);
    }
    cout << n - dp[1] << endl;
    return 0;
  }
};
class F1 {
 public:
  void solve() {
    int t;
    cin >> t;
    int n;
    while (t--) {
      cin >> n;
      vector<pair<long long, long long>> a(n);
      for (int i = 0; i < n; i++) {
        cin >> a[i].first;
        a[i].second = i + 1;
      }
      sort(a.begin(), a.end(),
           [](const pair<long long, long long>& a,
              const pair<long long, long long>& b) {
             if (a.first != b.first)
               return a.first < b.first;
             else
               return a.second > b.second;
           });
      deque<int> mono;
      stack<int> help;
      int ans = 0;
      for (int i = 0; i < n; i++) {
        if (i > 0 && a[i].first != a[i - 1].first) {
          while (!help.empty()) {
            mono.push_back(help.top());
            help.pop();
          }
        }
        while (!mono.empty() && a[mono.back()].second > a[i].second) {
          while (!mono.empty() && a[mono.front()].first < a[mono.back()].first)
            mono.pop_front();
          mono.pop_back();
        }
        help.push(i);
        ans = max(ans, (int)(help.size() + mono.size()));
      }
      cout << n - ans << endl;
    }
  }
};
class F2 {
 public:
  void solve() {
    int t;
    cin >> t;
    while (t--) {
      int n, id = 1;
      cin >> n;
      vector<vector<int>> dp(n + 1, vector<int>(3, 0));
      map<int, int> cnt;
      vector<int> a(n + 1), l(n + 1, n + 1), r(n + 1), nums(n + 1, 0);
      for (int i = 1; i <= n; i++) cin >> a[i];
      vector<int> b(a);
      sort(a.begin(), a.end());
      for (int i = 1; i <= n; i++) {
        if (!cnt.count(a[i])) cnt[a[i]] = id++;
        int cur = cnt[a[i]];
        nums[cur]++;
        l[cur] = min(l[cur], i);
        r[cur] = i;
      }
      int res = 0;
      vector<int> last(n + 1, 0);
      for (int i = 1; i <= n; i++) {
        int cur = cnt[b[i]];
        dp[i][0] = dp[last[cur]][0] + 1;
        dp[i][1] = max(dp[last[cur]][1] + 1,
                       max(dp[last[cur - 1]][0] + 1, dp[last[cur - 1]][2] + 1));
        if (r[cur] == i) {
          dp[i][2] = dp[l[cur]][1] + nums[cur] - 1;
        }
        last[cur] = i;
        for (int j = 0; j < 3; j++) res = max(res, dp[i][j]);
      }
      cout << n - res << endl;
    }
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  F1 ans;
  ans.solve();
  return 0;
}
