有 $$$n$$$ 彩色球排列成一排。这些球涂有 $$$n$$$ 不同的颜色,用从 $$$1$$$ 到 $$$n$$$ 的数字表示。左边第 $$$i$$$ 个球被涂成颜色 $$$c_i$$$。您想要对球重新排序,以便左侧第 $$$i$$$ 球的颜色为 $$$i$$$。此外,您还有 $$$k \ge 1$$$ 个颜色为 $$$0$$$ 的球,可以在重新排序过程中使用。
由于球的奇怪特性,只能通过执行以下操作来重新排序:
1. 将一个颜色 $$$0$$$ 的球放置在序列中的任何位置(任意两个连续球之间、最左边的球之前或最右边的球之后),同时保持其他球的相对顺序。您执行此操作的次数不得超过 $$$k$$$ 次,因为您只有 $$$k$$$ 个颜色为 $$$0$$$ 的球。
2. 选择任何非零颜色的球,使得与他相邻的至少一个球的颜色为 $$$0$$$,并将该球(非零颜色)移动到序列中的任何位置(任意两个连续的球之间、最左边的球之前或最右边的球之后),同时保持其他球的相对顺序。您可以根据需要多次执行此操作,但每次操作您应支付 $$$1$$$ 硬币。
您可以按任意顺序执行这些操作。最后一次操作后,所有 $$$0$$$ 颜色的球神奇地消失,留下一系列非零颜色的 $$$n$$$ 球。
在第二种类型的操作中,您应该花费多少金币才能使左边第 $$$i$$$ 个球在所有颜色为零的球消失后,从 $$$1$$$ 到 $$$n$$$ 的所有 $$$i$$$ 具有颜色 $$$i$$$?可以证明,在问题的约束下,总是可以按照所需的方式对球重新排序。
解决从 $$$1$$$ 到 $$$n$$$ 的所有 $$$k$$$ 的问题。
输入
第一行包含整数 $$$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$$$ 所需的方式重新排序球。
示例
输入 #1
3 6 2 3 1 4 6 5 3 1 2 3 11 7 3 4 6 8 9 10 2 5 11 1
输出 #1
3 2 2 2 2 2 0 0 0 10 5 4 4 4 4 4 4 4 4 4
注意
在第一个测试用例中,有 $$$n = 6$$$ 球。球的颜色从左到右为$$$[\, 2, 3, 1, 4, 6, 5 \,]$$$。
假设 $$$k = 1$$$。以 $$$3$$$ 硬币所需的方式重新排列球的方法之一:
$$$[\, 2, 3, 1, 4, 6, 5 \,]$$$ $$$\xrightarrow{\, 1 \,}$$$ $$$[\, 2, 3, 1, 4, \color{红色}{0}, 6, 5 \,]$$$ $$$\xrightarrow{\, 2 \,}$$$ $$$[\, 2, 3, \color{蓝色}{4}, 1, 0, 6, 5 \,]$$$ $$$\xrightarrow{\, 2 \,}$$$ $$$[\, \color{蓝色}{1}, 2, 3, 4, 0, 6, 5 \,]$$$ $$$\xrightarrow{\, 2\,}$$$ $$$[\, 1, 2, 3, 4, 0, 5, \颜色{蓝色}{6} \,]$$$
箭头上方的数字是操作类型。在第一种类型的操作中插入的球以红色突出显示;在第二类操作中移动的球以蓝色突出显示。
可以证明,对于 $$$k = 1$$$,不可能用少于 $$$3$$$ 的硬币以正确的顺序重新排列球。
假设 $$$k = 2$$$。以 $$$2$$$ 硬币所需的方式重新排列球的方法之一:
$$$[\, 2, 3, 1, 4, 6, 5 \,]$$$ $$$\xrightarrow{\, 1 \,}$$$ $$$[\, 2, 3, 1, 4, 6, \color{红色}{0}, 5\,]$$$ $$$\xrightarrow{\, 2 \,}$$$ $$$[\, 2, 3, 1, 4, 0, 5, \color{蓝色}{6}\,]$$$ $$$\xrightarrow{\, 1 \,}$$$ $$$[\, 2, 3, \color{红色}{0}, 1, 4, 0, 5, 6 \,]$$$ $$$\xrightarrow{\, 2 \,}$$$ $$$[\, \颜色{蓝色}{1}, 2, 3, 0, 4, 0, 5, 6\,]$$$
请注意,对于大于 $$$2$$$ 的 $$$k$$$,此操作顺序也是正确的。
可以证明,对于从 $$$2$$$ 到 $$$6$$$ 的 $$$k$$$,不可能用少于 $$$2$$$ 的硬币以正确的顺序重新排列球。
在第二个测试用例中,球已经按正确的顺序放置,因此所有 $$$k$$$ 的答案都等于 $$$0$$$。