Minimize Inversions Number
Contest: Codeforces Global Round 19
Difficulty rating: 3500
Tags: data structures, greedy, math, sortings

You are given a permutation $$$p$$$ of length $$$n$$$.

You can choose any subsequence, remove it from the permutation, and insert it at the beginning of the permutation keeping the same order.

For every $$$k$$$ from $$$0$$$ to $$$n$$$, find the minimal possible number of inversions in the permutation after you choose a subsequence of length exactly $$$k$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 50\,000$$$) — the number of test cases.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the length of the permutation.

The second line of each test case contains the permutation $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$).

It is guaranteed that the total sum of $$$n$$$ doesn't exceed $$$5 \cdot 10^5$$$.

Output format:
For each test case output $$$n + 1$$$ integers. The $$$i$$$-th of them must be the answer for the subsequence length of $$$i - 1$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the second test case:

- For the length $$$0$$$: $$$[4, 2, 1, 3] \rightarrow [4, 2, 1, 3]$$$: $$$4$$$ inversions.
- For the length $$$1$$$: $$$[4, 2, \mathbf{1}, 3] \rightarrow [1, 4, 2, 3]$$$: $$$2$$$ inversions.
- For the length $$$2$$$: $$$[4, \mathbf{2}, \mathbf{1}, 3] \rightarrow [2, 1, 4, 3]$$$, or $$$[4, 2, \mathbf{1}, \textbf{3}] \rightarrow [1, 3, 4, 2]$$$: $$$2$$$ inversions.
- For the length $$$3$$$: $$$[4, \mathbf{2}, \mathbf{1}, \mathbf{3}] \rightarrow [2, 1, 3, 4]$$$: $$$1$$$ inversion.
- For the length $$$4$$$: $$$[\mathbf{4}, \mathbf{2}, \mathbf{1}, \mathbf{3}] \rightarrow [4, 2, 1, 3]$$$: $$$4$$$ inversions.

Example input:
3
1
1
4
4 2 1 3
5
5 1 3 2 4

Example output:
0 0
4 2 2 1 4
5 4 2 2 1 5

Editorial:
To simplify the explanation, we will represent a permutation as a set of points $$$(i, p_i)$$$.
$$$\bf{Lemma}$$$: Let's consider some selected subsequence. Then there always exists such sequence of the same length, so that if we select it instead, the number of inversions won't increase, for which the following condition is satisfied: if the point $$$i$$$ is selected, then all points to the right and below point $$$i$$$ are also selected.
$$$\bf{Proof}$$$: Let assume that it's not right, then there is a pair of points $$$(i, j)$$$ such that $$$i$$$ is selected and $$$j$$$ is not, and j is to the right and below point $$$i$$$ (the point is selected if it is in the sequence). Let's call such pair a bad pair. Divide the points into 9 regions by 4 straight lines parallel to the coordinate axes passing through the point $$$i$$$ and $$$j$$$. No for every point, considering if it is selected or not and considering the region where it is, let's determine by how many it reduces the number of inversions after replacing $$$i$$$ with $$$j$$$ (i.e. select $$$j$$$ instead of $$$i$$$). Let's call it a contribution of this point. Also note that after replacing the point $$$i$$$ with the point $$$j$$$, the inversion formed by these two points disappears.
Note that negative contribution has only selected points, located between the point $$$i$$$ and $$$j$$$ (on the $$$Ox$$$ axis) above the point $$$i$$$, and unselected points located between the point $$$i$$$ and $$$j$$$ below the point $$$j$$$.
Now let's find any bad pair $$$(i, j)$$$ and do the following:
1. If there is a selected point $$$id$$$, which has negative contribution, then set $$$i = id$$$ and continue the algorithm.
2. Otherwise, if there is a unselected point $$$id$$$, which has negative contribution, then set $$$j = id$$$ and continue the algorithm.
3. Otherwise, after replacing the point $$$i$$$ with the point $$$j$$$ the number of inversions will reduce.
This algorithm always finds a bad pair such that after replacing $$$i$$$ with $$$j$$$ the number of inversions will reduce, because each time the value $$$j - i$$$ reduces. Q.E.D.
Let $$$d_i$$$ is a number by which the number of inversions will decrease after moving only the element with index $$$i$$$ to the beginning. Then $$$d_i =$$$ (the number of points to the left and above i$$$) - ($$$the number of points to the left and below i). Then, if sequence $$$seq$$$ is selected, then the number of inversions in a new permutation will be equal to $$$invs - \sum_{i \in seq} d_i + seqInvs - (\frac{|seq| \cdot (|seq| - 1)}{2} - seqInvs) = invs - \sum_{i \in seq} d_i + 2 \cdot seqInvs - \frac{|seq| \cdot (|seq| - 1)}{2}$$$. Here $$$invs$$$ — the number of inversions in the initial permutation, and $$$seqInvs$$$ — the number of inversions over all elements in the $$$seq$$$.
$$$seqInvs = \sum_{i \in seq}$$$ (the number of selected points to the right and below $$$i$$$). Due to the lemma proved above, if the sequence $$$seq$$$ is optimal, then if the point $$$i$$$ is selected, then $$$\Rightarrow$$$ all points to the right and below $$$i$$$ are selected as well, so if $$$s_i$$$ is the number of points to the right and below $$$i$$$, then $$$seqInvs = \sum_{i \in seq} s_i$$$. So the number of inversions in the new permutation equals to $$$invs - \sum_{i \in seq} (d_i - 2s_i) - \frac{|seq| \cdot (|seq| - 1)}{2}$$$. Note, that this formula can be incorrect if the sequence is not optimal. In this case point $$$i$$$ reduces the number of inversions by $$$c_i = d_i - 2s_i$$$.
Note that the number of points to the left and below $$$i$$$ equals to $$$p_i - 1 - s_i$$$, and the number of points to the left and above $$$i$$$ equals to $$$(i - 1) - (p_i - 1 - s_i) = i - p_i + s_i$$$. So $$$d_i = (i - p_i + s_i) - (p_i - 1 - s_i) = i - 2p_i + 2s_i + 1$$$. So $$$c_i = d_i - 2s_i = i - 2p_i + 1$$$.
Now it's not hard to see, that if the point $$$j$$$ is to the left and below the point $$$i$$$, then $$$c_j > c_i$$$. So if we select $$$len$$$ maximum elements by the value of $$$c_i$$$, the formula for the number of inversions written above is correct. It means that it is optimal. It can be implemented in $$$O(n \log{n})$$$.