CF1525B Permutation Sort

给定一个由 $n$ 个数 $1, 2, \ldots, n$ 组成的排列 $a$（排列是一个数组，其中每个 $1$ 到 $n$ 的元素恰好出现一次）。 你可以进行如下操作：选择 $a$ 的某个子数组（连续子段），并以任意方式重新排列其中的元素。但该操作不能作用于整个数组。 例如，如果 $a = [2, 1, 4, 5, 3]$，你想对子数组 $a[2, 4]$（即从第 $2$ 个到第 $4$ 个元素的子数组）进行操作，那么操作后数组可以变为 $a = [2, 5, 1, 4, 3]$，或者 $a = [2, 1, 5, 4, 3]$ 等等。 你的任务是计算，将排列 $a$ 排成升序所需的最少操作次数。

第一行包含一个整数 $t$（$1 \le t \le 2000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 50$），表示排列的元素个数。 每个测试用例的第二行包含 $n$ 个互不相同的整数，表示给定的排列 $a$，这些整数是 $1$ 到 $n$ 的一个排列。

对于每个测试用例，输出一个整数，表示将数组 $a$ 排成升序所需的最少操作次数。

在解释中，$a[i, j]$ 表示从第 $i$ 个元素到第 $j$ 个元素的子数组。 在第一个样例中，你可以选择子数组 $a[2, 3]$ 并交换其中的元素。 在第二个样例中，排列已经有序，因此不需要进行任何操作。 在第三个样例中，你可以选择子数组 $a[3, 5]$ 并重新排列其中的元素，使 $a$ 变为 $[2, 1, 3, 4, 5]$，然后选择子数组 $a[1, 2]$ 并交换其中的元素，使 $a$ 变为 $[1, 2, 3, 4, 5]$。 由 ChatGPT 4.1 翻译