给你一个整数 $$$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]$$$。