CF1839D Ball Sorting

有 $n$ 个彩球排成一排。这些球被涂成 $n$ 种不同的颜色，颜色编号为 $1$ 到 $n$。从左到右第 $i$ 个球的颜色为 $c_i$。你希望重新排列这些球，使得从左到右第 $i$ 个球的颜色为 $i$。 此外，你有 $k \ge 1$ 个颜色为 $0$ 的球，可以在重新排列过程中使用。 由于这些球具有奇特的性质，只能通过以下操作进行重新排列： 1. 在序列中的任意位置（任意两个相邻球之间、最左边之前或最右边之后）插入一个颜色为 $0$ 的球，同时保持其他球的相对顺序。由于你只有 $k$ 个颜色为 $0$ 的球，这个操作最多只能执行 $k$ 次。 2. 选择任意一个非零颜色的球，且该球至少有一个相邻球的颜色为 $0$，然后将该球移动到序列中的任意位置（任意两个相邻球之间、最左边之前或最右边之后），同时保持其他球的相对顺序。这个操作可以执行任意多次，但每执行一次需要支付 $1$ 个硬币。 你可以以任意顺序执行这些操作。最后一次操作后，所有颜色为 $0$ 的球会神奇地消失，留下 $n$ 个非零颜色的球。 请问，为了使所有颜色为 $0$ 的球消失后，从左到右第 $i$ 个球的颜色为 $i$，你最少需要为第 2 种操作花费多少硬币？可以证明，在本题的约束条件下，总是可以通过上述操作将球排列成所需顺序。 请你对于所有 $k$ 从 $1$ 到 $n$ 的情况，分别求出所需花费的最小硬币数。

第一行包含一个整数 $t$（$1 \le t \le 500$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 500$），表示球的数量。 第二行包含 $n$ 个两两不同的整数 $c_1, c_2, \ldots, c_n$（$1 \le c_i \le n$），表示从左到右每个球的颜色。 保证所有测试用例中 $n$ 的总和不超过 $500$。

对于每个测试用例，输出 $n$ 个整数，第 $i$ 个（$1 \le i \le n$）表示当 $k = i$ 时，将球重新排列成所需顺序所需支付的最小硬币数。

在第一个测试用例中，有 $n = 6$ 个球。从左到右的颜色为 $[\, 2, 3, 1, 4, 6, 5 \,]$。 假设 $k = 1$。一种用 $3$ 个硬币完成目标的操作方式如下： $[\, 2, 3, 1, 4, 6, 5 \,]$ $\xrightarrow{\, 1 \,}$ $[\, 2, 3, 1, 4, \color{red}{0}, 6, 5 \,]$ $\xrightarrow{\, 2 \,}$ $[\, 2, 3, \color{blue}{4}, 1, 0, 6, 5 \,]$ $\xrightarrow{\, 2 \,}$ $[\, \color{blue}{1}, 2, 3, 4, 0, 6, 5 \,]$ $\xrightarrow{\, 2\,}$ $[\, 1, 2, 3, 4, 0, 5, \color{blue}{6} \,]$ 箭头上方的数字表示操作类型。用第一种操作插入的球用红色标出；用第二种操作移动的球用蓝色标出。 可以证明，对于 $k = 1$，无法用少于 $3$ 个硬币完成目标。 假设 $k = 2$。一种用 $2$ 个硬币完成目标的操作方式如下： $[\, 2, 3, 1, 4, 6, 5 \,]$ $\xrightarrow{\, 1 \,}$ $[\, 2, 3, 1, 4, 6, \color{red}{0}, 5\,]$ $\xrightarrow{\, 2 \,}$ $[\, 2, 3, 1, 4, 0, 5, \color{blue}{6}\,]$ $\xrightarrow{\, 1 \,}$ $[\, 2, 3, \color{red}{0}, 1, 4, 0, 5, 6 \,]$ $\xrightarrow{\, 2 \,}$ $[\, \color{blue}{1}, 2, 3, 0, 4, 0, 5, 6\,]$ 注意，这一操作序列对于 $k$ 大于 $2$ 也同样适用。 可以证明，对于 $k$ 从 $2$ 到 $6$，无法用少于 $2$ 个硬币完成目标。 在第二个测试用例中，球已经按正确顺序排列，因此所有 $k$ 的答案都是 $0$。 由 ChatGPT 4.1 翻译