Minimize Inversions Number solution codeforces

Minimize Inversions Number solution codeforces

SOLUTION:- CLICK HERE

You are given a permutation pp of length nn.

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 kk from 00 to nn, find the minimal possible number of inversions in the permutation after you choose a subsequence of length exactly kk.

Input

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

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

The second line of each test case contains the permutation p1,p2,,pnp1,p2,…,pn (1pin1≤pi≤n).

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

Output

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

Example
input

Copy
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
Note

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.

SOLUTION:- CLICK HERE

Leave a Comment

Your email address will not be published.