[Solution] Minimize Inversions Number solution codeforces

Minimize Inversions Number solution codeforces – 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 00 to 𝑛n, find the minimal possible number of inversions in the permutation after you choose a subsequence of length exactly 𝑘k.

Minimize Inversions Number solution codeforces

The first line contains a single integer 𝑡t (1𝑡500001≤t≤50000) — the number of test cases.

The first line of each test case contains one integer 𝑛n (1𝑛51051≤n≤5⋅105) — the length of the permutation.

The second line of each test case contains the permutation 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn (1𝑝𝑖𝑛1≤pi≤n).

It is guaranteed that the total sum of 𝑛n doesn’t exceed 51055⋅105.

Output

For each test case output 𝑛+1n+1 integers. The 𝑖i-th of them must be the answer for the subsequence length of 𝑖1i−1.

Minimize Inversions Number solution codeforces

3
1
1
4
4 2 1 3
5
5 1 3 2 4
output

Copy
0 0
4 2 2 1 4
5 4 2 2 1 5

Minimize Inversions Number solution codeforces

In the second test case:

  • For the length 00[4,2,1,3][4,2,1,3][4,2,1,3]→[4,2,1,3]44 inversions.
  • For the length 11[4,2,1,3][1,4,2,3][4,2,1,3]→[1,4,2,3]22 inversions.
  • For the length 22[4,2,1,3][2,1,4,3][4,2,1,3]→[2,1,4,3], or [4,2,1,3][1,3,4,2][4,2,1,3]→[1,3,4,2]22 inversions.
  • For the length 33[4,2,1,3][2,1,3,4][4,2,1,3]→[2,1,3,4]11 inversion.
  • For the length 44[4,2,1,3][4,2,1,3][4,2,1,3]→[4,2,1,3]44 inversions.

Leave a Comment