← 返回题目列表

Codeforces · 1986/E

E. 美丽的阵列

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

给定一个整数数组 $$$a_1、a_2、\ldots、a_n$$$ 和一个整数 $$$k$$$。你需要用最少的操作让它变得漂亮。

在应用操作之前,您可以根据需要对数组元素进行打乱。对于一项操作,您可以执行以下操作:

- 选择一个索引 $$$1 \leq i \leq n$$$,
- 使 $$$a_i = a_i + k$$$。

如果 $$$b_i = b_{n - i + 1}$$$ 对于所有 $$$1 \leq i \leq n$$$ 来说,数组 $$$b_1, b_2, \ldots, b_n$$$ 是美丽的。

求使数组美观所需的最少操作数,否则报告不可能。

输入

每个测试都包含多组输入数据。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 输入数据的组数。然后是他们的描述。

每组输入数据的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq k \leq 10^9$$$) - 数组 $$$a$$$ 的大小和问题陈述中的数字 $$$k$$$。

每组输入数据的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组 $$$a$$$ 的元素。

保证所有输入数据集的 $$$n$$$ 之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每组输入数据,输出使数组美观所需的最少操作次数,如果不可能则输出$$$-1$$$。

示例

输入 #1

11
1 1000000000
1
2 1
624323799 708290323
3 1
3 2 1
4 1
7 1 5 3
5 1
11 2 15 7 10
7 1
1 8 2 16 8 16 31
13 1
2 1 1 3 3 11 12 22 45 777 777 1500 74
10 2
1 2 1 2 1 2 1 2 1 2
11 2
1 2 1 2 1 2 1 2 1 2 1
13 3
2 3 9 14 17 10 22 20 18 30 1 4 28
5 1
2 3 5 3 5

输出 #1

0
83966524
1
4
6
1
48
-1
0
14
0

注意

在第一组输入数据中,数组已经很漂亮了。

在第二组输入数据中,您可以在操作之前对数组进行打乱,并执行索引 $$$i = 1$$$ 的操作 $$$83966524$$$ 次。

在第三组输入数据中,您可以对数组 $$$a$$$ 进行打乱,使其等于 $$$[2, 3, 1]$$$。然后应用索引$$$i = 3$$$的操作得到数组$$$[2, 3, 2]$$$,这很漂亮。

在第八组输入数据中,没有一组操作,也没有办法对元素进行打乱以使数组变得漂亮。

在第九组输入数据中,数组已经很漂亮了。