Вам дана перестановка$$$^{\text{∗}}$$$ $$$p$$$ размером $$$n$$$.
Ваша задача — найти перестановку $$$q$$$ размером $$$n$$$ такую, что $$$\operatorname{GCD}$$$$$$^{\text{†}}$$$$$$(p_i+q_i, p_{i+1}+q_{i+1}) \geq 3$$$ для всех $$$1 \leq i \lt n$$$. Другими словами, наибольший общий делитель суммы любых двух соседних позиций должен быть не менее $$$3$$$.
Можно показать, что это всегда возможно.
$$$^{\text{∗}}$$$Перестановкой длины $$$m$$$ является массив, состоящий из $$$m$$$ различных целых чисел от $$$1$$$ до $$$m$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$m=3$$$, но в массиве встречается $$$4$$$).
$$$^{\text{†}}$$$$$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \leq p_i \leq n$$$).
Гарантируется, что данный массив образует перестановку.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите перестановку $$$q$$$ в новой строке. Если есть несколько возможных ответов, вы можете вывести любой.
331 3 255 1 2 4 376 7 1 5 4 3 2
2 3 1 4 5 1 2 3 2 1 3 7 5 6 4
В первом наборе входных данных, $$$\operatorname{GCD}(1+2,3+3)=3\geq 3$$$ и $$$\operatorname{GCD}(3+3,2+1)=3\geq3$$$, так что вывод правильный.
| Codeforces Round 1047 (Div. 3) |
|---|
| Закончено |
