← 返回题目列表

Codeforces · 1823/B

B. 按步骤排序

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

让我们将长度 $$$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$$$ 进行排序。