Монокарп — маленький мальчик, который живет в Байтландии и любит программировать.
Недавно он нашел перестановку длины \(n\). Он должен придумать странную перестановку. Это должна быть новая перестановка, отличающаяся от старой в каждой позиции.
Более формально, если старая перестановка равна \(p_1,p_2,\ldots,p_n\), а новая — \(q_1,q_2,\ldots,q_n\), то должно выполняться \(\)p_1\neq q_1, p_2\neq q_2, \ldots ,p_n\neq q_n.\(\)
Монокарп боится лексикографически больших перестановок. Не могли бы вы помочь ему найти лексикографически минимальную странную перестановку?
Примечание
В первом наборе входных данных всевозможными странными перестановками являются \([2,3,1]\) и \([3,1,2]\). Лексикографически меньшая из них равна \([2,3,1]\).
Во втором наборе входных данных \([1,2,3,4,5]\) — это лексикографически минимально возможная перестановка, и она является странной.
В третьем наборе входных данных возможные странные перестановки: \([1,2,4,3]\), \([1,4,2,3]\), \([1,4,3,2]\), \([3,1,4,2]\), \([3,2,4,1]\), \([3,4,2,1]\), \([4,1,2,3]\), \([4,1,3,2]\) и \([4,3,2,1]\). Минимальная из них — \([1,2,4,3]\).