Лиса любит перестановки! Она придумала следующую задачу, и предложила Коту её решить:
Вам дано четное целое положительное число \(n\) и перестановка\(^\dagger\) \(p\) длины \(n\).
Счет другой перестановки \(q\) длины \(n\) определим как количество локальных максимумов в массиве \(a\) длины \(n\), где \(a_i = p_i + q_i\) для всех индексов \(i\) (\(1 \le i \le n\)). Другими словами, счет \(q\) — это количество \(i\) таких, что \(1 < i < n\) (обратите внимание на строгие неравенства), \(a_{i-1} < a_i\) и \(a_i > a_{i+1}\) (еще раз обратите внимание на строгие неравенства).
Найдите перестановку \(q\), которая достигает максимального счета при заданных \(n\) и \(p\). Если таких перестановок несколько, вы можете вывести любую из них.
\(^\dagger\) Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) — не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую любую перестановку чисел длины \(n\) (массив \(q\)) такую, что счёт \(q\) максимален при заданных ограничениях.
Примечание
В первом примере \(a = [3, 6, 4, 7]\). Массив имеет только один локальный максимум (на второй позиции), поэтому счет выбранной перестановки \(q\) равен \(1\). Можно доказать, что этот счет оптимален при заданных ограничениях.
В последнем примере полученный массив \(a = [6, 6, 12, 7, 14, 7, 14, 6]\) имеет \(3\) максимума — на третьей, пятой и седьмой позициях.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
1 2 3 4
4
4 3 1 2
6
6 5 1 4 2 3
8
1 2 4 5 7 6 8 3
|
2 4 1 3
3 1 4 2
2 5 1 4 3 6
5 4 8 2 7 1 6 3
|