Minimize Inversions Number

题意翻译

给定一个 $1\sim n$ 的排列 $p$。 你可以进行下列操作正好一次： - 选定 $p$ 的一个长度为 $k$ 的子序列，并将其按照相同的顺序移动到 $p$ 的最前面。 对于 $k=0,1,\cdots,n$，分别求出 $p$ 在操作后的最小逆序对数。 每个测试点包含 $T$ 组数据。 保证： $1\leq T\leq5\times10^4;$ $1\leq n,\sum n\leq5\times10^5;$ $p$ 是一个 $1\sim n$ 的排列。

题目描述

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 $ .

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

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

说明

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.