#include <bits/stdc++.h>
using std::abs;
using std::array;
using std::cerr;
using std::cin;
using std::cout;
using std::generate;
using std::get;
using std::make_pair;
using std::make_tuple;
using std::map;
using std::max;
using std::max_element;
using std::min;
using std::min_element;
using std::pair;
using std::queue;
using std::reverse;
using std::set;
using std::sort;
using std::string;
using std::swap;
using std::tuple;
using std::unique;
using std::vector;
template <typename T>
T input() {
  T res;
  cin >> res;
  {};
  return res;
}
template <typename IT>
void input_seq(IT b, IT e) {
  std::generate(b, e,
                input<typename std::remove_reference<decltype(*b)>::type>);
}
int main() {
  std::iostream::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  for (int t = input<int>(); t != 0; --t) {
    int n = input<int>();
    vector<int> a(n);
    input_seq(a.begin(), a.end());
    map<int, vector<int>> where;
    for (int i = 0; i < n; ++i) where[a[i]].push_back(i);
    set<pair<int, int>> on;
    int fuck = 0;
    int ans = int((where).size());
    auto L = where.rbegin();
    auto R = where.rbegin();
    int cur = 0;
    while (L != where.rend()) {
      for (auto elem : L->second) {
        auto it = on.emplace(make_pair(elem, a[elem])).first;
        if (it != on.begin() and std::prev(it)->second > a[elem]) ++fuck;
        if (std::next(it) != on.end() and a[elem] > std::next(it)->second)
          ++fuck;
        if (it != on.begin() and std::next(it) != on.end() and
            std::prev(it)->second > std::next(it)->second)
          --fuck;
      }
      ++L;
      ++cur;
      while (fuck and R != where.rend()) {
        for (auto elem : R->second) {
          auto it = on.emplace(make_pair(elem, a[elem])).first;
          if (it != on.begin() and std::prev(it)->second > a[elem]) --fuck;
          if (std::next(it) != on.end() and a[elem] > std::next(it)->second)
            --fuck;
          if (it != on.begin() and std::next(it) != on.end() and
              std::prev(it)->second > std::next(it)->second)
            ++fuck;
          on.erase(it);
        }
        ++R;
        --cur;
      }
      if (not fuck) ans = min(ans, int((where).size()) - cur);
    }
    cout << ans << "\n";
  }
  return 0;
}
