CF1367F1 Flying Sort (Easy Version)

这是该问题的简单版本。在本版本中，给定数组中的所有数字均不相同，并且 $n$ 的限制比难版本更小。 给定一个长度为 $n$ 的整数数组 $a$（数组中没有相等的元素）。你可以对数组元素进行以下操作： 1. 选择任意下标 $i$（$1 \le i \le n$），将元素 $a[i]$ 移动到数组的开头； 2. 选择任意下标 $i$（$1 \le i \le n$），将元素 $a[i]$ 移动到数组的末尾。 例如，如果 $n = 5$，$a = [4, 7, 2, 3, 9]$，则可以进行如下操作序列： - 对第二个元素执行第一种操作后，数组 $a$ 变为 $[7, 4, 2, 3, 9]$； - 对第二个元素执行第二种操作后，数组 $a$ 变为 $[7, 2, 3, 9, 4]$。 你可以以任意顺序、任意次数地执行任意类型的操作。 请你求出，使数组 $a$ 变为非递减有序（即满足 $a[1] \le a[2] \le \ldots \le a[n]$）所需的最少操作次数（第一种和第二种操作的总次数）。

第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来有 $t$ 组测试用例。 每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 3000$），表示数组 $a$ 的长度。 接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$），表示需要通过上述操作排序的数组。给定数组中的所有数字均不相同。 所有测试用例中 $n$ 的总和不超过 $3000$。

对于每个测试用例，输出一个整数，表示使数组变为非递减有序所需的最少操作次数（第一种和第二种操作的总次数）。

在第一个测试用例中，你需要先将 3 移到开头，然后将 2 移到开头。因此，操作序列为：$[4, 7, 2, 3, 9] \rightarrow [3, 4, 7, 2, 9] \rightarrow [2, 3, 4, 7, 9]$。 在第二个测试用例中，你需要将 1 移到开头，将 8 移到末尾。因此，操作序列为：$[3, 5, 8, 1, 7] \rightarrow [1, 3, 5, 8, 7] \rightarrow [1, 3, 5, 7, 8]$。 在第三个测试用例中，数组已经是有序的。 由 ChatGPT 4.1 翻译