← 返回题目列表

Codeforces · 1617/C

C. 辣椒粉和排列

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

Paprika 喜欢排列。她有一个数组 $$$a_1, a_2, \dots, a_n$$$。她想让数组成为整数 $$$1$$$ 到 $$$n$$$ 的排列。

为了达到这个目的,她可以对数组进行操作。在每个操作中,她可以选择两个整数 $$$i$$$ ($$$1 \le i \le n$$$) 和 $$$x$$$ ($$$x > 0$$$),然后执行 $$$a_i := a_i \bmod x$$$ (即将 $$$a_i$$$ 替换为 $$$a_i$$$ 除以 $$$x$$$ 的余数)。在不同的操作中,选择的$$$i$$$和$$$x$$$可以不同。

确定使数组成为整数 $$$1$$$ 到 $$$n$$$ 的排列所需的最少操作数。如果不可能,则输出$$$-1$$$。

排列是由从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数组成的数组,按任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。

输入

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

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

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

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

输出

对于每个测试用例,输出使数组成为整数排列 $$$1$$$ 到 $$$n$$$ 所需的最少操作数,如果不可能,则输出 $$$-1$$$。

示例

输入 #1

4
2
1 7
3
1 5 4
4
12345678 87654321 20211218 23571113
9
1 2 3 4 18 19 5 6 7

输出 #1

1
-1
4
2

注意

对于第一个测试,最小化操作数量的唯一可能的操作顺序是:

- 选择$$$i=2$$$, $$$x=5$$$。执行 $$$a_2 := a_2 \bmod 5 = 2$$$。

对于第二个测试,不可能获得从 $$$1$$$ 到 $$$n$$$ 的整数排列。