给定一个整数数组 $$$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]$$$,这很漂亮。
在第八组输入数据中,没有一组操作,也没有办法对元素进行打乱以使数组变得漂亮。
在第九组输入数据中,数组已经很漂亮了。