#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int q;
  cin >> q;
  while (q--) {
    int n;
    cin >> n;
    vector<int> a(n);
    set<int> s;
    map<int, int> compress;
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
      s.insert(a[i]);
    }
    int cnt = 1;
    for (auto it : s) {
      compress[it] = cnt;
      ++cnt;
    }
    --cnt;
    vector<int> first(cnt + 5, -1), last(cnt + 5);
    for (int i = 0; i < n; ++i) {
      int x = compress[a[i]];
      last[x] = i;
      if (first[x] == -1) {
        first[x] = i;
      }
    }
    first[cnt + 1] = 1e9;
    int ans = 1e9;
    set<int>::iterator itr;
    vector<int> dp(cnt + 5, 0);
    itr = s.end();
    --itr;
    for (;; --itr) {
      int x = *itr;
      x = compress[x];
      if (last[x] < first[x + 1]) {
        dp[x] = dp[x + 1] + 1;
      } else {
        dp[x] = 1;
      }
      ans = min(ans, cnt - dp[x]);
      if (itr == s.begin()) break;
    }
    cout << ans << "\n";
  }
  return 0;
}
