CF1839D.Ball Sorting

There are $n$ colorful balls arranged in a row. The balls are painted in $n$ distinct colors, denoted by numbers from $1$ to $n$. The $i$-th ball from the left is painted in color $c_i$. You want to reorder the balls so that the $i$-th ball from the left has color $i$. Additionally, you have $k \ge 1$ balls of color $0$ that you can use in the reordering process.

Due to the strange properties of the balls, they can be reordered only by performing the following operations:

1. Place a ball of color $0$ anywhere in the sequence (between any two consecutive balls, before the leftmost ball or after the rightmost ball) while keeping the relative order of other balls. You can perform this operation no more than $k$ times, because you have only $k$ balls of color $0$.
2. Choose any ball of non-zero color such that at least one of the balls adjacent to him has color $0$, and move that ball (of non-zero color) anywhere in the sequence (between any two consecutive balls, before the leftmost ball or after the rightmost ball) while keeping the relative order of other balls. You can perform this operation as many times as you want, but for each operation you should pay $1$ coin.

You can perform these operations in any order. After the last operation, all balls of color $0$ magically disappear, leaving a sequence of $n$ balls of non-zero colors.

What is the minimum amount of coins you should spend on the operations of the second type, so that the $i$-th ball from the left has color $i$ for all $i$ from $1$ to $n$ after the disappearance of all balls of color zero? It can be shown that under the constraints of the problem, it is always possible to reorder the balls in the required way.

Solve the problem for all $k$ from $1$ to $n$.

有 $n$ 个彩色小球排成一行。这些小球被涂上了 $n$ 种互不相同的颜色，用 $1$ 到 $n$ 的整数表示。从左往右数第 $i$ 个小球的颜色为 $c_i$。你希望重新排列这些小球，使得从左往右数第 $i$ 个小球的颜色恰好为 $i$。此外，你还有 $k \ge 1$ 个颜色为 $0$ 的小球，可在重排过程中使用。

由于这些小球具有特殊的物理性质，你只能通过以下两种操作来重排它们：

1. 将一个颜色为 $0$ 的小球插入序列中任意位置（可插入任意两个相邻小球之间、最左侧之前或最右侧之后），同时保持其余小球的相对顺序不变。由于你仅有 $k$ 个颜色为 $0$ 的小球，该操作最多执行 $k$ 次。
2. 任选一个颜色非零的小球，要求其至少有一个相邻小球的颜色为 $0$；然后将该（非零色）小球移动到序列中任意位置（可插入任意两个相邻小球之间、最左侧之前或最右侧之后），同时保持其余小球的相对顺序不变。该操作可执行任意多次，但每次需花费 $1$ 枚金币。

你可以以任意顺序执行上述操作。所有操作完成后，所有颜色为 $0$ 的小球会自动消失，最终剩下 $n$ 个颜色非零的小球组成的序列。

问：对于每个 $k = 1, 2, \dots, n$，为使最终序列满足“从左往右数第 $i$ 个小球颜色为 $i$”（对所有 $i = 1, 2, \dots, n$ 成立），你最少需要在第 2 类操作上花费多少枚金币？可以证明，在本题约束条件下，总能以某种方式完成所需重排。

The first line contains integer $t$ ($1 \le t \le 500$) — the number of test cases. The descriptions of the test cases follow.

The first line contains one integer $n$ ($1 \le n \le 500$) — the number of balls.

The second line contains $n$ distinct integers $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le n$) — the colors of balls from left to right.

It is guaranteed that sum of $n$ over all test cases doesn't exceed $500$.

第一行包含一个整数 $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$。

For each test case, output $n$ integers: the $i$-th ($1 \le i \le n$) of them should be equal to the minimum amount of coins you need to spend in order to reorder balls in the required way for $k = i$.

对于每个测试用例，输出 $n$ 个整数：其中第 $i$ 个整数（$1 \le i \le n$）应等于当 $k = i$ 时，为将球重新排列成所需顺序所需的最少硬币花费。

In the first test case there are $n = 6$ balls. The colors of the balls from left to right are $[\, 2, 3, 1, 4, 6, 5 \,]$.

Let's suppose $k = 1$. One of the ways to reorder the balls in the required way for $3$ coins:

$[\, 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} \,]$

The number above the arrow is the operation type. Balls inserted on the operations of the first type are highlighted red; balls moved on the operations of second type are highlighted blue.

It can be shown that for $k = 1$ it is impossible to rearrange balls in correct order for less than $3$ coins.

Let's suppose $k = 2$. One of the ways to reorder the balls in the required way for $2$ coins:

$[\, 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\,]$

Note that this sequence of operations is also correct for $k$ greater than $2$.

It can be shown that for $k$ from $2$ to $6$ it is impossible to rearrange balls in correct order for less than $2$ coins.

In the second test case the balls are already placed in the correct order, so answers for all $k$ are equal to $0$.

第一个测试用例中有 $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\,]$

注意：该操作序列对所有大于 2 的 $k$ 值也成立。

可以证明：当 $k$ 取 $2$ 至 $6$ 之间的任意整数时，无法以少于 2 枚硬币的代价将球排列成正确顺序。

在第二个测试用例中，球已处于正确顺序，因此对所有 $k$，答案均为 $0$。