Перестановка длины \(n\) — это массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — это перестановка, но \([1,2,2]\) — это не перестановка (\(2\) встречается дважды в массиве), а \([1,3,4]\) также не является перестановкой (\(n=3\), но в массиве встречается \(4\)).
Пусть \(p\) — перестановка длины \(n\). Определим подпись \(F(p)\) перестановки \(p\) как отсортированный массив сумм соседних элементов \(p\). Более формально,
\(\)F(p)=\mathrm{sort}([p_1+p_2,p_2+p_3,\ldots,p_{n-1}+p_n]).\(\)
Например, если \(n=4\) и \(p=[1,4,2,3],\) тогда подпись будет вычисляться следующим образом: \(F(p)=\mathrm{sort}([1+4,4+2,2+3])=\mathrm{sort}([5,6,5])=[5,5,6]\).
Вам дана перестановка \(p\) длины \(n\). Ваша задача найти какую-то другую перестановку \(p'\) с такой же подписью. Обратите внимание, что перестановки \(p\) и \(p'\) обязаны различаться хотя бы в одной позиции, то есть должна существовать такая позиция \(i\), что \(p_i \ne p'_i\).
Выходные данные
Для каждого набора входных данных, выведите \(n\) целых чисел \(p'_1,\ldots, p'_n\) — перестановку, удовлетворяющую следующим условиям: \(p'\ne p\) и \(F(p')=F(p)\).
Можно доказать, что для любой перестановки, удовлетворяющей ограничениям из условия, существует ответ.
Если правильных ответов несколько, можно вывести любой.
Примечание
В первом примере \(F(p)=\mathrm{sort}([1+2])=[3]\).
И \(F(p')=\mathrm{sort}([2+1])=[3]\).
Во втором примере \(F(p)=\mathrm{sort}([2+1,1+6,6+5,5+4,4+3])=\mathrm{sort}([3,7,11,9,7])=[3,7,7,9,11]\).
И \(F(p')=\mathrm{sort}([1+2,2+5,5+6,6+3,3+4])=\mathrm{sort}([3,7,11,9,7])=[3,7,7,9,11]\).
В третьем примере \(F(p)=\mathrm{sort}([2+4,4+3,3+1,1+5])=\mathrm{sort}([6,7,4,6])=[4,6,6,7]\).
И \(F(p')=\mathrm{sort}([3+1,1+5,5+2,2+4])=\mathrm{sort}([4,6,7,6])=[4,6,6,7]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
1 2
6
2 1 6 5 4 3
5
2 4 3 1 5
|
2 1
1 2 5 6 3 4
3 1 5 2 4
|