彩球排序

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定 $1$ 到 $n$ 的一个排列。可插入至多 $k$ 个颜色为零的球；与零球相邻的非零球可以花费一枚硬币移动到任意位置。所有零球最后消失。

对每个 $k=1,2,\ldots,n$，求把排列变成 $1,2,\ldots,n$ 的最少花费。

输入格式

第一行包含测试组数 $t$。每组第一行包含 $n$，第二行包含排列 $c$。所有测试组的 $n$ 之和不超过 $500$。

输出格式

对每组输出 $n$ 个整数，第 $k$ 个整数对应可使用 $k$ 个零球时的答案。

样例输入 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

数据范围

• $1\le t\le500$，$1\le n\le500$；
• $c$ 是 $1$ 到 $n$ 的排列；
• 所有测试组的 $n$ 之和不超过 $500$。