Определим перестановкой длины \(n\) массив \(p\) длины \(n\), в котором каждое число от \(1\) до \(n\) встречается единожды.
Вам дана перестановка \(p_1, p_2, \dots, p_n\) и число \(k\). Вам необходимо отсортировать перестановку в возрастающем порядке. Для этого вы можете выполнить следующую операцию любое количество раз (возможно, ни разу):
- выбрать два элемента перестановки \(p_i\) и \(p_j\) такие, что \(|i - j| = k\) и поменять их местами.
К сожалению, некоторые перестановки не могут быть отсортированы для некоторых \(k\). Например, невозможно отсортировать \([2, 4, 3, 1]\) для \(k = 2\).
Поэтому, перед началом сортировки, вы можете выполнить не более одного предварительного обмена:
- выбрать любую пару \(p_i\) и \(p_j\) и поменять их местами.
Ваша задача проверить:
- возможно ли отсортировать перестановку без предварительных обменов,
- если нет, проверить, возможно ли отсортировать перестановку с использованием ровно одного предварительного обмена.
Например, если \(k = 2\) и дана перестановка \([2, 4, 3, 1]\), то вы можете выполнить предварительный обмен \(p_1\) и \(p_4\), что даст перестановку \([1, 4, 3, 2]\), которую уже можно отсортировать для данного \(k\).
Выходные данные
Для каждого набора входных данных выведите
- 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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
0
0
1
0
1
-1
|