Вам дана перестановка \(a\) размера \(n\), и вы должны выполнить над ней \(n\) операций. В \(i\)-й операции вы должны выбрать непустой суффикс \(a\) и увеличить все его элементы на \(i\). Каким образом нужно выполнить операции, чтобы минимизировать количество инверсий в конечном массиве?
Обратите внимание, что вы можете выполнять операции с одним и тем же суффиксом любое количество раз.
Перестановкой размера \(n\) называется такой массив размера \(n\), где каждое целое число от \(1\) до \(n\) встречается ровно один раз. Суффиксом называются несколько последовательных элементов массива, включающие в себя последний элемент массива. Инверсией в массиве \(a\) называется пара индексов \((i, j)\) такая, что \(i > j\) и \(a_{i} < a_{j}\).
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел \(x_{1}, x_{2}, \ldots, x_{n}\) (\(1 \le x_{i} \le n\) для каждого \(1 \le i \le n\)), указывающее, что \(i\)-я операция должна быть применена к суффиксу начиная с индекса \(x_{i}\). Если ответов несколько, выведите любой из них.
Примечание
В первом наборе входных данных одно из оптимальных решений — на каждой операции увеличивать весь массив (то есть суффикс, начинающийся с индекса \(1\)). Итоговый массив \([11, 12, 13, 14]\) будет содержать \(0\) инверсий.
Во втором наборе входных данных \(a\) будет равно \([2, 4, 3, 5, 6]\), \([2, 4, 3, 7, 8]\), \([2, 4, 6, 10, 11]\), \([2, 8, 10, 14, 15]\) и \([7, 13, 15, 19, 20]\) после первой, второй, третьей, четвертой и пятой операций соответственно. Таким образом, итоговый массив \(a\) будет иметь ноль инверсий.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
1 2 3 4
5
1 3 2 4 5
3
2 3 1
1
1
|
1 1 1 1
1 4 3 2 1
1 3 3
1
|