给你一个长度为 $$$n$$$ 的排列$$$^\dagger$$$ $$$p$$$。
在一次操作中,您可以选择两个索引 $$$1 \le i < j \le n$$$ 并将 $$$p_i$$$ 与 $$$p_j$$$ 交换。
求在排列中恰好有一次反转$$$^\ddagger$$$ 所需的最少操作数。
$$$^\dagger$$$ 排列是由从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数以任意顺序组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
$$$^\ddagger$$$ 排列 $$$p$$$ 的反转数是满足 $$$1 \le i < j \le n$$$ 且 $$$p_i > p_j$$$ 的索引对 $$$(i, j)$$$ 的数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1,p_2,\ldots, p_n$$$ ($$$1 \le p_i \le n$$$)。保证 $$$p$$$ 是一个排列。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 在排列中恰好有一个反转所需的最少操作数。可以证明答案总是存在的。
示例
输入 #1
4 2 2 1 2 1 2 4 3 4 1 2 4 2 4 3 1
输出 #1
0 1 3 1
注意
在第一个测试用例中,排列已经满足条件。
在第二个测试用例中,您可以执行 $$$(i,j)=(1,2)$$$ 运算,之后的排列将是 $$$[2,1]$$$ ,它只有一个反转。
在第三个测试用例中,不可能用少于 $$$3$$$ 的操作来满足条件。然而,如果我们执行 $$$3$$$ 操作,其中 $$$(i,j)$$$ 依次为 $$$(1,3)$$$、$$$(2,4)$$$ 和 $$$(3,4)$$$,则最终排列将是 $$$[1, 2, 4, 3]$$$,它只有一个反转。
在第四个测试用例中,您可以执行 $$$(i,j)=(2,4)$$$ 的运算,之后的排列将是 $$$[2,1,3,4]$$$,只有一个反转。