← 返回题目列表

Codeforces · 1863/B

B. 拆分排序

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

给你一个整数 $$$1$$$ 到 $$$n$$$ 的排列$$$^{\dagger}$$$ $$$p_1, p_2, \ldots, p_n$$$。

您可以通过多次(可能为零)应用以下操作来更改当前排列:

- 选择一些$$$x$$$ ($$$2 \le x \le n$$$);
- 创建一个新的排列:首先,写下 $$$p$$$ 中小于 $$$x$$$ 的所有元素,不改变它们的顺序; 其次,写下$$$p$$$中大于或等于$$$x$$$的所有元素,不改变它们的顺序;
- 用新创建的排列替换 $$$p$$$。

例如,如果排列过去是 $$$[6, 4, 3, 5, 2, 1]$$$ 并且您选择 $$$x = 4$$$,那么您将首先写下 $$$[3, 2, 1]$$$,然后在后面加上 $$$[6, 4, 5]$$$。因此初始排列将被替换为 $$$[3, 2, 1, 6, 4, 5]$$$。

找出当 $$$i = 1, 2, \ldots, n$$$ 时实现 $$$p_i = i$$$ 所需的最少操作数。我们可以证明,这样做总是有可能的。

$$$^{\dagger}$$$ 长度 $$$n$$$ 的排列是一个数组,由 $$$n$$$ 不同的整数组成,从 $$$1$$$ 到 $$$n$$$ 的任意顺序。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100\,000$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$)。保证 $$$p_1, p_2, \ldots, p_n$$$ 是一个排列。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$100\,000$$$。

输出

对于每个测试用例,在单独的行上输出答案。

示例

输入 #1

5
1
1
2
2 1
6
6 4 3 5 2 1
3
3 1 2
19
10 19 7 1 17 11 8 5 12 9 4 18 14 2 6 15 3 16 13

输出 #1

0
1
4
1
7

注意

在第一个测试用例中,$$$n = 1$$$ 且 $$$p_1 = 1$$$,因此无需执行任何操作。

在第二个测试用例中,我们可以选择$$$x = 2$$$,我们立即得到$$$p_1 = 1$$$,$$$p_2 = 2$$$。

在第三个测试用例中,我们可以通过以下方式实现最少的操作数:

1. $$$x = 4$$$: $$$[6, 4, 3, 5, 2, 1] \rightarrow [3, 2, 1, 6, 4, 5]$$$;
2. $$$x = 6$$$: $$$[3, 2, 1, 6, 4, 5] \rightarrow [3, 2, 1, 4, 5, 6]$$$;
3. $$$x = 3$$$: $$$[3, 2, 1, 4, 5, 6] \rightarrow [2, 1, 3, 4, 5, 6]$$$;
4. $$$x = 2$$$: $$$[2, 1, 3, 4, 5, 6] \rightarrow [1, 2, 3, 4, 5, 6]$$$。