说明

在一个圆桌旁坐着 $n$ 个人，编号从 $1$ 到 $n$。每个编号为 $i$ 的人的右边是编号为 $i+1$ 的人（如果 $i=n$，则右边是编号为 $1$ 的人）。

现在你打算重新安排他们的座位，这个新安排由排列 $p_1, p_2, \dots, p_n$ 描述。目标是让编号为 $p_{i+1}$ 的人坐在编号为 $p_i$ 的人的右边（编号为 $p_1$ 的人位于编号为 $p_n$ 的人的右边）。注意，座位的排列方式可以通过旋转得到 $n$ 种不同的表示。

为了实现这个目标，你可以交换两个相邻的人的座位，但有一个限制：对于所有 $1 \le x \le n-1$，你不能交换编号为 $x$ 和编号为 $x+1$ 的人（不过，你可以交换编号为 $n$ 和编号为 $1$ 的人）。找出达成最终座位顺序所需的最少交换次数。可以证明，无论初始顺序如何，任何目标安排都是可以实现的。

输入格式

输入包含多个测试用例。第一行是一个整数 $t$ ($1 \le t \le 10\,000$)，表示测试用例的数量。接下来的部分是 $t$ 个测试用例的详细描述。

每个测试用例的第一行是一个整数 $n$ ($3 \le n \le 200\,000$)，表示圆桌旁的人数。

第二行是一个排列 $p_1, p_2, \dots, p_n$，每个整数各不相同且 $1 \le p_i \le n$，表示希望达成的最终座位顺序。

所有测试用例中，$n$ 的总和不超过 $200\,000$。

输出格式

对于每个测试用例，输出实现目标顺序所需的最少交换次数。

3
4
2 3 1 4
5
5 4 3 2 1
7
4 1 6 5 3 7 2

1
10
22

提示

本翻译由 AI 自动生成