CF1907F.Shift and Reverse

Given an array of integers $a_1, a_2, \ldots, a_n$. You can make two types of operations with this array:

• Shift: move the last element of array to the first place, and shift all other elements to the right, so you get the array $a_n, a_1, a_2, \ldots, a_{n-1}$.
• Reverse: reverse the whole array, so you get the array $a_n, a_{n-1}, \ldots, a_1$.

Your task is to sort the array in non-decreasing order using the minimal number of operations, or say that it is impossible.

给定一个整数数组 $a_1, a_2, \ldots, a_n$。你可以对这个数组执行以下两种操作：

• 移位（Shift）：将数组的最后一个元素移动到最前面，其余所有元素向右平移一位，从而得到新数组 $a_n, a_1, a_2, \ldots, a_{n-1}$。
• 翻转（Reverse）：将整个数组反转，从而得到新数组 $a_n, a_{n-1}, \ldots, a_1$。

你的任务是使用最少的操作次数将该数组按非递减顺序排序；若无法实现，则说明这是不可能的。

The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Descriptions of test cases follow.

The first line of each test case contains an integer $n$ ($1\le n \le 10^5$) — size of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — elements of the array.

It is guaranteed that sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\le n \le 10^5$）—— 表示数组的大小。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）—— 表示数组的元素。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case output the number $k$, the minimal number of operations you need to sort the array. If it is impossible to sort the array using these operations, output $-1$.

对于每个测试用例，输出数字 $k$，即对数组进行排序所需的最少操作次数。如果无法通过这些操作对数组进行排序，则输出 $-1$。

In the first test case of the example, to sort the array [$3, 2, 1, 5, 4$] you need to perform $3$ operations:

• Shift to obtain the array [$4, 3, 2, 1, 5$];
• Shift to obtain the array [$5, 4, 3, 2, 1$];
• Reverse to obtain the array [$1, 2, 3, 4, 5$].

In the third test case of the example, it can be shown that it is impossible to sort the array using the given operations.

In the seventh test case of the example, to sort the array [$4, 1, 3, 4, 4$] you need to perform $3$ operations:

• Reverse to obtain the array [$4, 4, 3, 1, 4$];
• Shift to obtain the array [$4, 4, 4, 3, 1$];
• Reverse to obtain the array [$1, 3, 4, 4, 4$].

在示例的第一个测试用例中，要将数组 [$3, 2, 1, 5, 4$] 排序，需要执行 $3$ 次操作：

• 执行一次移位操作，得到数组 [$4, 3, 2, 1, 5$]；
• 执行一次移位操作，得到数组 [$5, 4, 3, 2, 1$]；
• 执行一次翻转操作，得到数组 [$1, 2, 3, 4, 5$]。

在示例的第三个测试用例中，可以证明：无法使用给定的操作对数组进行排序。

在示例的第七个测试用例中，要将数组 [$4, 1, 3, 4, 4$] 排序，需要执行 $3$ 次操作：

• 执行一次翻转操作，得到数组 [$4, 4, 3, 1, 4$]；
• 执行一次移位操作，得到数组 [$4, 4, 4, 3, 1$]；
• 执行一次翻转操作，得到数组 [$1, 3, 4, 4, 4$]。