Дано положительное целое число \(n\).
Найдите перестановку \(a_1, a_2, \dots, a_n\) такую, что для любых \(1 \leq l < r \leq n\) сумма \(a_l + a_{l+1} + \dots + a_r\) не делится на \(r-l+1\).
Перестановка длины \(n\) — это массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) является перестановкой, но \([1,2,2]\) не является перестановкой (число \(2\) встречается дважды в массиве), и \([1,3,4]\) также не является перестановкой (при \(n=3\) в массиве есть число \(4\)).
Выходные данные
Для каждого набора входных данных, если такой перестановки не существует, выведите \(-1\).
В противном случае выведите \(n\) различных целых чисел \(p_1, p_{2}, \dots, p_n\) (\(1 \leq p_i \leq n\)) — перестановку, удовлетворяющую условию, описанному в задаче.
Если есть несколько решений, выведите любое из них.
Примечание
В первом примере подходящих пар \(l < r\) нет совсем, из чего следует, что условие выполнено для всех возможных пар.
Во втором примере единственная допустимая пара — это \(l=1\) и \(r=2\), для которых \(a_1 + a_2 = 1+2=3\) не делится на \(r-l+1=2\).
В третьем примере, для \(l=1\) и \(r=3\) сумма \(a_1+a_2+a_3\) всегда равна \(6\). Она делится на \(3\), поэтому такой перестановки не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
2
3
|
1
1 2
-1
|