有$$$n$$$个人,编号从$$$1$$$到$$$n$$$,坐在圆桌旁。人 $$$i+1$$$ 坐在人 $$$i$$$ 的右边(人 $$$1$$$ 坐在人 $$$n$$$ 的右边)。
你已经想出了一个更好的座位安排,它以排列 $$$p_1, p_2, \dots, p_n$$$ 的形式给出。更具体地说,您想要更改人员的座位,以便最终 $$$p_{i+1}$$$ 坐在 $$$p_i$$$ 人员的右侧($$$p_1$$$ 坐在 $$$p_n$$$ 人员的右侧)。请注意,对于每个座位安排,都有描述它的 $$$n$$$ 排列(可以通过轮换获得)。
为了实现这一点,你可以交换坐在相邻位置的两个人;但有一个问题:对于所有 $$$1 \le x \le n-1$$$ ,你不能交换 person $$$x$$$ 和 person $$$x+1$$$ (请注意,你可以交换 person $$$n$$$ 和 person $$$1$$$ )。所需的最少交换次数是多少?可以证明,任何安排都可以实现。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10\,000$$$) — 测试用例的数量。 $$$t$$$ 测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 200\,000$$$) — 坐在桌子旁的人数。
第二行包含 $$$n$$$ 不同的整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$, $$$p_i \ne p_j$$$ for $$$i \ne j$$$) — 桌子周围的人所需的最终顺序。
所有测试用例的 $$$n$$$ 值的总和不超过 $$$200\,000$$$。
输出
对于每个测试用例,打印实现所需顺序所需的最小交换次数。
示例
输入 #1
3 4 2 3 1 4 5 5 4 3 2 1 7 4 1 6 5 3 7 2
输出 #1
1 10 22
注意
在第一个测试用例中,我们可以在初始配置中交换 person $$$4$$$ 和 person $$$1$$$ (相邻的),并得到与所需顺序等效的 $$$[4, 2, 3, 1]$$$ 顺序。因此在这种情况下,一次交换就足够了。