读写要求

本题采用文件读写，请在提交代码时使用正确的文件读写方式，否则会导致 RE

输入：sort.in

输出：sort.out

题目描述

给定一个长度为 $n$ 的数组 $a$，其中所有元素互不相同。你可以执行以下两种操作任意次：

1. 选择任意下标 $i$，将 $a_i$ 移动到数组最前端；
2. 选择任意下标 $i$，将 $a_i$ 移动到数组最末端。

求使得数组变为非递减顺序所需的最少操作次数。

例如 $n=5$, $a=[4,7,2,3,9]$：

• 先将 $3$ 移到最前：$[3,4,7,2,9]$
• 再将 $2$ 移到最前：$[2,3,4,7,9]$

总共 $2$ 次操作。

输入格式

第一行一个整数 $t$，表示测试用例组数。($1\le t\le 100$)

每组测试数据第一行一个整数 $n$ ($1\le n\le 3000$)

第二行 $n$ 个互不相同的整数 $a_1,a_2,\dots,a_n$ ($0\le a_i\le 10^9$)

所有测试用例的 $n$ 之和不超过 $3000$。

输出格式

对每组测试数据，输出一行一个整数，表示最少操作次数。

输入输出样例

4
5
4 7 2 3 9
5
3 5 8 1 7
5
1 4 5 7 12
4
0 2 1 3

2
2
0
2