Sắp xếp bằng cách dời đầu cuối

Cho mảng $a$ gồm $n$ số nguyên (mảng có thể chứa các phần tử bằng nhau). Bạn được phép thực hiện hai loại thao tác:

1. Chọn một chỉ số $i$ bất kỳ ($1\le i\le n$) và chuyển phần tử $a_i$ lên đầu mảng.
2. Chọn một chỉ số $i$ bất kỳ ($1\le i\le n$) và chuyển phần tử $a_i$ xuống cuối mảng.

Ví dụ với $n=5$, $a=[4,7,2,2,9]$: sau khi áp dụng thao tác loại 1 lên phần tử thứ hai, mảng trở thành $[7,4,2,2,9]$; tiếp đó áp dụng thao tác loại 2 lên phần tử thứ hai, mảng trở thành $[7,2,2,9,4]$.

Bạn có thể thực hiện các thao tác thuộc hai loại trên với số lần tùy ý, theo thứ tự tùy ý.

Hãy tìm số thao tác ít nhất cần thực hiện để mảng $a$ được sắp xếp không giảm, tức là $a_1\le a_2\le \dots \le a_n$.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $t$: số lượng bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng:
  • Dòng thứ nhất chứa số nguyên $n$: kích thước mảng $a$.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên là số thao tác ít nhất cần thực hiện.

Ràng buộc

• $1\le t\le {10}^4$
• $1\le n\le 2·{10}^5$
• $0\le a_i\le {10}^9$
• Tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $2·{10}^5$.

Ví dụ