I wonder, does the falling rain
Forever yearn for it's disdain?
Effluvium of the Mind
Вам дано целое положительное число \(n\).
Найдите любую перестановку \(p\) длины \(n\) такую, что сумма \(\operatorname{lcm}(1,p_1) + \operatorname{lcm}(2, p_2) + \ldots + \operatorname{lcm}(n, p_n)\) максимальна.
Здесь \(\operatorname{lcm}(x, y)\) означает наименьшее общее кратное (НОК) двух чисел \(x\) и \(y\).
Перестановкой является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Выходные данные
Для каждого набора входных данных выведите \(n\) чисел \(p_1\), \(p_2\), \(\ldots\), \(p_n\) — перестановку с максимально возможным значением \(\operatorname{lcm}(1,p_1) + \operatorname{lcm}(2, p_2) + \ldots + \operatorname{lcm}(n, p_n)\).
Если существуют несколько решений, выведите любое из них.
Примечание
Для \(n = 1\), существует только одна перестановка, поэтому ответ — \([1]\).
Для \(n = 2\), существует две перестановки:
- \([1, 2]\) — сумма равна \(\operatorname{lcm}(1,1) + \operatorname{lcm}(2, 2) = 1 + 2 = 3\).
- \([2, 1]\) — сумма равна \(\operatorname{lcm}(1,2) + \operatorname{lcm}(2, 1) = 2 + 2 = 4\).