← 返回题目列表

Codeforces · 1662/E

E. 圆桌会议

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

有$$$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]$$$ 顺序。因此在这种情况下,一次交换就足够了。