Statement is not available in English language
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 \lt j$$$ и $$$p_i \gt 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$$$ пары, расположенные в неправильном порядке.