让我们将长度 $$$n$$$ 的排列定义为长度 $$$n$$$ 的数组 $$$p$$$,其中包含从 $$$1$$$ 到 $$$n$$$ 的每个数字恰好一次。
给你一个排列 $$$p_1, p_2, \dots, p_n$$$ 和一个数字 $$$k$$$。您需要按升序排列此排列。为此,您可以重复以下操作任意次数(可能为零):
- 选择排列 $$$p_i$$$ 和 $$$p_j$$$ 的两个元素,使得 $$$|i - j| = k$$$,然后交换它们。
不幸的是,某些排列无法用某些固定数字 $$$k$$$ 进行排序。例如,不可能使用 $$$k = 2$$$ 对 $$$[2, 4, 3, 1]$$$ 进行排序。
因此,在开始排序之前,你最多可以进行一次初步交换:
- 选择任意对 $$$p_i$$$ 和 $$$p_j$$$ 并交换它们。
您的任务是:
1. 检查是否可以在不进行任何初步交换的情况下对排列进行排序,
2. 如果不是,请检查是否可以仅使用一次初步交换对排列进行排序。
例如,如果$$$k = 2$$$,排列为$$$[2, 4, 3, 1]$$$,则可以对$$$p_1$$$和$$$p_4$$$进行初步交换,这将产生排列$$$[1, 4, 3, 2]$$$,可以用给定的$$$k$$$进行排序。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le n - 1$$$) - 排列的长度,以及可以交换的元素之间的距离。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — 排列 $$$p$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10 ^ 5$$$。
输出
对于每个测试用例打印
- 0,如果可以在不进行初步交换的情况下对排列进行排序;
- 1,如果可以通过一次初步交换对排列进行排序,但如果没有初步交换则不可能;
- -1,如果无法通过最多一次初步交换对排列进行排序。
示例
输入 #1
6 4 1 3 1 2 4 4 2 3 4 1 2 4 2 3 1 4 2 10 3 4 5 9 1 8 6 10 2 3 7 10 3 4 6 9 1 8 5 10 2 3 7 10 3 4 6 9 1 8 5 10 3 2 7
输出 #1
0 0 1 0 1 -1
注意
在第一个测试用例中,不需要进行初步交换,因为可以交换$$$(p_1, p_2)$$$,然后交换$$$(p_2, p_3)$$$。
在第二个测试用例中,不需要进行初步交换,因为可以交换$$$(p_1, p_3)$$$,然后交换$$$(p_2, p_4)$$$。
在第三个测试用例中,您需要对$$$(p_2, p_3)$$$应用初步交换。之后,排列变为 $$$[3, 4, 1, 2]$$$,并且可以使用 $$$k = 2$$$ 进行排序。