Это простая версия задачи. Разница между простой и сложной версиями в том, что в этой версии вы можете вывести любую перестановку с наименьшим весом.
Вам дана перестановка \(p_1, p_2, \ldots, p_n\) целых чисел от \(1\) до \(n\).
Определим вес перестановки \(q_1, q_2, \ldots, q_n\) целых чисел от \(1\) до \(n\) как \(\)|q_1 - p_{q_{2}}| + |q_2 - p_{q_{3}}| + \ldots + |q_{n-1} - p_{q_{n}}| + |q_n - p_{q_{1}}|\(\)
Вы хотите, чтобы ваша перестановка была настолько легкой, насколько это возможно. Найдите любую перестановку \(q\) с наименьшим возможным весом.
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел \(q_1, q_2, \ldots, q_n\) (\(1 \le q_i \le n\), все \(q_i\) различны) — одну из перестановок с наименьшим весом.
Примечание
В первом наборе входных данных есть две перестановки длины \(2\): \((1, 2)\) и \((2, 1)\). Перестановка \((1, 2)\) имеет вес \(|1 - p_2| + |2 - p_1| = 0\), а перестановка \((2, 1)\) имеет тот же вес: \(|2 - p_1| + |1 - p_2| = 0\). В этой версии мы можем вывести любую из этих перестановок.
Во втором наборе входных данных вес перестановки \((1, 3, 4, 2)\) равен \(|1 - p_3| + |3 - p_4| + |4 - p_2| + |2 - p_1| = |1 - 1| + |3 - 4| + |4 - 3| + |2 - 2| = 2\). Перестановок с меньшими весами не существует.
В третьем наборе входных данных вес перестановки \((1, 4, 2, 3, 5)\) равен \(|1 - p_4| + |4 - p_2| + |2 - p_3| + |3 - p_5| + |5 - p_1| = |1 - 2| + |4 - 4| + |2 - 3| + |3 - 1| + |5 - 5| = 4\). Перестановок с меньшими весами не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
2 1
4
2 3 1 4
5
5 4 3 2 1
|
1 2
1 3 4 2
1 4 2 3 5
|