410265: GYM103994 G Split sort

G. Split sortограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Изучив все известные алгоритмы сортировки Лёша решил придумать свой собственный. Новый алгоритм он называет «split-sort». Его идея заключается в том, чтобы несколько раз применить к сортируемому массиву длины $$$n$$$ следующие три операции:

1. Выбрать число $$$k$$$ от $$$1$$$ до $$$n$$$.
2. Удалить некоторые $$$k$$$ элементов массива.
3. Приписать удаленные элементы в начало массива в обратном порядке.

Например, для массива [5, 1, 4, 2, 3] можно выбрать $$$k = 3$$$, удалить элементы $$$[1, 4, 3]$$$, после чего массив станет равным $$$[5, 2]$$$, а затем приписать удаленные в начало в обратном порядке, после чего массив станет равным $$$[3, 4, 1, 5, 2]$$$.

Леша всё ещё изучает свойства изобретенного алгоритма. Сейчас он пытается понять, как работа алгоритма зависит от выбора числа $$$k$$$. А именно, для данной перестановки $$$p$$$ чисел $$$1, 2, \dots, n$$$ и для каждого $$$k$$$ от $$$1$$$ до $$$n$$$ он хочет понять, какой минимальной неупорядоченности можно добиться, сделав одну операцию с данным $$$k$$$.

Перестановкой $$$p$$$ чисел $$$1, 2, \dots n$$$ называется массив $$$[p_1, p_2, \dots p_n]$$$, такой что $$$1 \le p_i \le n$$$ и $$$p_i \neq p_j$$$ при $$$i \neq j$$$

Неупорядоченностью перестановки $$$p$$$ Леша называет количество инверсий в ней, то есть количество таких пар $$$i$$$, $$$j$$$, что $$$i < j$$$ и $$$p_i > p_j$$$.

У Леши ещё очень много важных алгоритмов, которые он хочет обдумать, а потому изучение алгоритма «split-sort» он поручил вам, справитесь ли вы с такой задачей?

Входные данные

Первая строка содержит единственное целое число $$$n$$$ $$$(1 \le n \le 300\,000)$$$ — длину перестановки.

Вторая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n, p_i \neq p_j$$$, если $$$i \neq j$$$) — элементы перестановки.

Выходные данные

Выведите $$$n$$$ чисел, где $$$k$$$-е число равно минимальной неупорядоченности перестановки, которой можно добиться применением одной описанной выше операции с $$$k$$$ элементами.

ПримерыВходные данные

5
5 1 4 2 3

Выходные данные

5 4 4 4 4

Входные данные

5
1 2 3 4 5

Выходные данные

0 1 3 6 10

Входные данные

5
3 5 1 2 4

Выходные данные

3 2 2 3 5

Примечание

В первом примере:

1. При $$$k = 1$$$: выбираем элемент $$$[1]$$$: $$$[5, 1, 4, 2, 3] \rightarrow [5, 4, 2, 3] \rightarrow [1, 5, 4, 2, 3]$$$ — $$$5$$$ пар, расположенных в неправильном порядке.
2. При $$$k = 2$$$: выбираем элементы $$$[1, 2]$$$: $$$[5, 1, 4, 2, 3] \rightarrow [5, 4, 3] \rightarrow [2, 1, 5, 4, 3]$$$ — $$$4$$$ пары, расположенные в неправильном порядке.
3. При $$$k = 3$$$: выбираем элементы $$$[1, 2, 3]$$$: $$$[5, 1, 4, 2, 3] \rightarrow [5, 4] \rightarrow [3, 2, 1, 5, 4]$$$ — $$$4$$$ пары, расположенные в неправильном порядке.
4. При $$$k = 4$$$: выбираем элементы $$$[5, 1, 4, 2]$$$: $$$[5, 1, 4, 2, 3] \rightarrow [3] \rightarrow [2, 4, 1, 5, 3]$$$ — $$$4$$$ пары, расположенные в неправильном порядке.
5. При $$$k = 5$$$: выбираем элементы $$$[5, 1, 4, 2, 3]$$$: $$$[5, 1, 4, 2, 3] \rightarrow [] \rightarrow [3, 2, 4, 1, 5]$$$ — $$$4$$$ пары, расположенные в неправильном порядке.