← 返回题目列表

Codeforces · 1899/E

E. 队列排序

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

Vlad 找到了一个由 $$$n$$$ 整数组成的数组 $$$a$$$,并决定按非降序对其进行排序。

为此,Vlad 可以多次应用以下操作:

- 提取数组的第一个元素并将其插入到末尾;
- 将该元素与前一个元素交换,直到它成为第一个元素或直到它严格大于前一个元素。

请注意,这两个操作都是操作的一部分,对于一项操作,您必须应用这两个操作。

例如,如果对数组 [$$$4, 3, 1, 2, 6, 4$$$] 进行运算,则会发生如下变化:

- [$$$\颜色{红色}{4}, 3, 1, 2, 6, 4$$$];
- [$$$3, 1, 2, 6, 4, \color{红色}{4}$$$];
- [$$$3, 1, 2, 6, \color{红色}{4}, 4$$$];
- [$$$3, 1, 2, \color{红色}{4}, 6, 4$$$]。

Vlad 没有时间执行所有操作,因此他要求您确定对数组进行排序所需的最少操作数,否则报告不可能。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组的元素。

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

输出

对于每个测试用例,输出一个整数 - 对数组进行排序所需的最少操作数。如果不可能,则输出 $$$-1$$$ 作为答案。

示例

输入 #1

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

输出 #1

2
6
-1
-1
0