H. Минимизируй количество инверсий
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана перестановка $$$p$$$ длины $$$n$$$.

Можно выбрать любую её подпоследовательность, удалить её из перестановки и приписать в начало перестановки в том же порядке.

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

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 50\,000$$$) — количество наборов входных данных.

В первой строке каждого набора вводится число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — длина перестановки.

Во второй строке каждого набора вводится перестановка $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$).

Гарантируется, что сумма $$$n$$$ не превосходит $$$5 \cdot 10^5$$$.

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

Для каждого набора выведите $$$n + 1$$$ число, где $$$i$$$-е число — ответ на задачу для длины подпоследовательности, равной $$$i - 1$$$.

Пример
Входные данные
3
1
1
4
4 2 1 3
5
5 1 3 2 4
Выходные данные
0 0
4 2 2 1 4
5 4 2 2 1 5
Примечание

Во втором наборе:

  • Для длины $$$0$$$: $$$[4, 2, 1, 3] \rightarrow [4, 2, 1, 3]$$$: $$$4$$$ инверсии.
  • Для длины $$$1$$$: $$$[4, 2, \mathbf{1}, 3] \rightarrow [1, 4, 2, 3]$$$: $$$2$$$ инверсии.
  • Для длины $$$2$$$: $$$[4, \mathbf{2}, \mathbf{1}, 3] \rightarrow [2, 1, 4, 3]$$$ или $$$[4, 2, \mathbf{1}, \textbf{3}] \rightarrow [1, 3, 4, 2]$$$: $$$2$$$ инверсии.
  • Для длины $$$3$$$: $$$[4, \mathbf{2}, \mathbf{1}, \mathbf{3}] \rightarrow [2, 1, 3, 4]$$$: $$$1$$$ инверсия.
  • Для длины $$$4$$$: $$$[\mathbf{4}, \mathbf{2}, \mathbf{1}, \mathbf{3}] \rightarrow [4, 2, 1, 3]$$$: $$$4$$$ инверсии.