← 返回题目列表

Codeforces · 1907/F

F. 换档和反向

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

给定一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。您可以使用此数组进行两种类型的操作:

- 移位:将数组的最后一个元素移到第一个位置,并将所有其他元素向右移动,这样就得到数组 $$$a_n, a_1, a_2, \ldots, a_{n-1}$$$。
- 反转:反转整个数组,这样你就得到数组 $$$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$$$。

示例

输入 #1

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

输出 #1

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

注意

在示例的第一个测试用例中,要对数组 [$$$3, 2, 1, 5, 4$$$] 进行排序,您需要执行 $$$3$$$ 操作:

- 移位得到数组 [$$$4, 3, 2, 1, 5$$$];
- Shift 获取数组 [$$$5, 4, 3, 2, 1$$$];
- 逆向得到数组[$$$1, 2, 3, 4, 5$$$]。

在示例的第三个测试用例中,可以表明不可能使用给定的操作对数组进行排序。

在示例的第七个测试用例中,要对数组 [$$$4, 1, 3, 4, 4$$$] 进行排序,您需要执行 $$$3$$$ 操作:

- 反转得到数组[$$$4, 4, 3, 1, 4$$$];
- Shift 得到数组 [$$$4, 4, 4, 3, 1$$$];
- 逆向得到数组[$$$1, 3, 4, 4, 4$$$]。