#include <bits/stdc++.h>
using namespace std;
const int LEN = (int)3e5;
int q;
int n;
int a[LEN];
int l[LEN];
int r[LEN];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> q;
  while (q--) {
    cin >> n;
    memset(l, -1, sizeof(*l) * n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      a[i]--;
      if (l[a[i]] == -1) l[a[i]] = i;
      r[a[i]] = i;
    }
    int cntl = 0;
    int cntr = 0;
    set<int> rset;
    for (int i = 0; i < n; i++) cntr += l[i] != -1;
    int j = 0;
    for (; j < n; j++)
      if (l[j] != -1) {
        if (rset.empty() || (*rset.rbegin()) < l[j]) {
          rset.insert(r[j]);
          cntr--;
          continue;
        }
        break;
      }
    int ans = cntr;
    for (int i = 0; i < n; i++)
      if (l[i] != -1) {
        cntl++;
        rset.erase(r[i]);
        for (; j < n; j++)
          if (l[j] != -1) {
            if (rset.empty() || (*rset.rbegin()) < l[j]) {
              rset.insert(r[j]);
              cntr--;
              continue;
            }
            break;
          }
        ans = min(ans, cntl + cntr);
      }
    cout << ans << "\n";
  }
  return 0;
}
