Дана неотсортированная перестановка \(p_1, p_2, \ldots, p_n\). Чтобы отсортировать перестановку, выберите один раз целое число \(k\) (\(k \ge 1\)) и выполните некоторые операции над перестановкой. В одной операции вы можете выбрать два целых числа \(i\), \(j\) (\(1 \le j < i \le n\)) таких, что \(i - j = k\), затем поменять местами \(p_i\) и \(p_j\).
Какое максимальное значение \(k\) вы можете выбрать, чтобы отсортировать данную перестановку?
Перестановка — это массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2, 3, 1, 5, 4]\) — это перестановка, но \([1, 2, 2]\) не является перестановкой (\(2\) появляется дважды в массиве), а \([1, 3, 4]\) также не является перестановкой (\(n = 3\), но в массиве есть \(4\)).
Неотсортированная перестановка \(p\) — это такая перестановка, что существует хотя бы одна позиция \(i\), которая удовлетворяет условию \(p_i \ne i\).
Выходные данные
Для каждого набора входных данных выведите максимальное значение \(k\), которое вы можете выбрать, чтобы отсортировать данную перестановку.
Мы можем показать, что ответ всегда существует.
Примечание
В первом наборе входных данных максимальное значение \(k\), которое вы можете выбрать, равно \(1\). Операции, используемые для сортировки перестановки:
- Поменять местами \(p_2\) и \(p_1\) (\(2 - 1 = 1\)) \(\rightarrow\) \(p = [1, 3, 2]\)
- Поменять местами \(p_2\) и \(p_3\) (\(3 - 2 = 1\)) \(\rightarrow\) \(p = [1, 2, 3]\)
Во втором наборе входных данных максимальное значение \(k\), которое вы можете выбрать, равно \(2\). Операции, используемые для сортировки перестановки:
- Поменять местами \(p_3\) и \(p_1\) (\(3 - 1 = 2\)) \(\rightarrow\) \(p = [1, 4, 3, 2]\)
- Поменять местами \(p_4\) и \(p_2\) (\(4 - 2 = 2\)) \(\rightarrow\) \(p = [1, 2, 3, 4]\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3
3 1 2
4
3 4 1 2
7
4 2 6 7 5 3 1
9
1 6 7 4 9 2 3 8 5
6
1 5 3 4 2 6
10
3 10 5 2 9 6 7 8 1 4
11
1 11 6 4 8 3 7 5 9 10 2
|
1
2
3
4
3
2
3
|