CF1637H Minimize Inversions Number

给定一个长度为 $n$ 的排列 $p$。 你可以选择任意一个子序列，将其从排列中移除，并保持其原有顺序插入到排列的开头。 对于每个 $k$，$0 \leq k \leq n$，求在选择长度恰好为 $k$ 的子序列后，排列中可能的最小逆序对数。

第一行包含一个整数 $t$（$1 \leq t \leq 50\,000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 5 \cdot 10^5$），表示排列的长度。 第二行包含排列 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$）。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

对于每个测试用例，输出 $n+1$ 个整数，第 $i$ 个数表示选择长度为 $i-1$ 的子序列后，排列中可能的最小逆序对数。

在第二个测试用例中： - 长度为 $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$。 由 ChatGPT 4.1 翻译