310910: CF1907F. Shift and Reverse

F. Shift and Reversetime limit per test2.0 smemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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$.

ExampleInput

11
5
3 2 1 5 4
5
1 1 2 1 1
4
3 7 10 5
5
1 2 3 4 5
2
5 1
3
3 4 1
5
4 1 3 4 4
3
5 1 1
4
2 5 5 4
5
2 2 1 1 2
2
5 5

Output

3
2
-1
0
1
1
3
1
2
2
0

Note

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$].

题目大意：
给定一个整数数组 \(a_1, a_2, \ldots, a_n\)。可以对这个数组进行两种操作：
1. 移位：将数组的最后一个元素移动到第一个位置，并将所有其他元素向右移动，得到数组 \(a_n, a_1, a_2, \ldots, a_{n-1}\)。
2. 反转：反转整个数组，得到数组 \(a_n, a_{n-1}, \ldots, a_1\)。

任务是使用最少的操作次数将数组排序为非递减顺序，或者判断是否不可能。

输入数据格式：
第一行输入包含一个整数 \(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\)。

输出数据格式：
对于每个测试用例，输出一个整数 \(k\)，表示将数组排序所需的最少操作次数。如果使用这些操作无法对数组进行排序，则输出 \(-1\)。题目大意： 给定一个整数数组 \(a_1, a_2, \ldots, a_n\)。可以对这个数组进行两种操作： 1. 移位：将数组的最后一个元素移动到第一个位置，并将所有其他元素向右移动，得到数组 \(a_n, a_1, a_2, \ldots, a_{n-1}\)。 2. 反转：反转整个数组，得到数组 \(a_n, a_{n-1}, \ldots, a_1\)。 任务是使用最少的操作次数将数组排序为非递减顺序，或者判断是否不可能。 输入数据格式： 第一行输入包含一个整数 \(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\)。 输出数据格式： 对于每个测试用例，输出一个整数 \(k\)，表示将数组排序所需的最少操作次数。如果使用这些操作无法对数组进行排序，则输出 \(-1\)。