← 返回题目列表

Codeforces · 1525/B

B. 排列排序

中文机器翻译题面 查看原题

给你一个排列 $$$a$$$,由 $$$n$$$ 数字 $$$1$$$、$$$2$$$、...、$$$n$$$ 组成(排列是一个数组,其中从 $$$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$$$) — 排列中的元素数量。

测试用例的第二行包含从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数 - 给定的排列 $$$a$$$。

输出

对于每个测试用例,输出一个整数 - 如上所述对数组 $$$a$$$ 按升序排序的最少操作数。

示例

输入 #1

3
4
1 3 2 4
3
1 2 3
5
2 1 4 5 3

输出 #1

1
0
2

注意

在解释中,$$$a[i, j]$$$ 定义 $$$a$$$ 的子数组,从第 $$$i$$$ 个元素开始,到第 $$$j$$$ 个元素结束。

在示例的第一个测试用例中,您可以选择子数组 $$$a[2, 3]$$$ 并交换其中的元素。

在示例的第二个测试用例中,排列已经排序,因此您不需要应用任何操作。

在示例的第三个测试用例中,您可以选择子数组 $$$a[3, 5]$$$ 并重新排序其中的元素,使 $$$a$$$ 变为 $$$[2, 1, 3, 4, 5]$$$,然后选择子数组 $$$a[1, 2]$$$ 并交换其中的元素,使 $$$a$$$ 变为$$$[1,2,3,4,5]$$$。