#P2304A. Yet another permutation problem

Yet another permutation problem

本题没有可用的提交语言。

QAQ

这是本场最难的题,请不要按顺序开题!

背景

众所周知,Permutation\mathtt{Permutation} (排列) 问题在 codeforces\mathtt{codeforces} 平台上随处可见,考虑到其高度的可塑性,Ocean 打算扔一题给你《玩玩》。

我们定义长度为 nn 的排列为一个长度为 nn 的数组,包含元素 1,2,,n1, 2, \ldots, n,且不存在重复元素。

{1,5,4,2,3}\{1, 5, 4, 2, 3\} 为长度为 55 的排列,而 {1,6,4,2,3}\{1, 6, 4, 2, 3\}{1,2,2,4,5}\{1, 2, 2, 4, 5\} 不是。

说明

现在,在你眼前的是一个长度为 nn 的排列 aa。排列的顺序很杂乱,所以 Ocean 打算将其升序排序。

但是,显然简单的排序算法并不能让 Ocean 满足,所以他想到了一个更有意思的排列方式!

首先,我们有如下的两个操作:

  1. 选择任意位置,插入一个 00
  2. 如果一个元素和 00 相邻,那么这个元素可以移动到任意位置。

我们记第一个操作可以被执行恰好 kk 次,那么你需要找出操作 22 的最少执行次数 cntcnt,使最后的序列去除 00 后升序。

O宝 觉得这题有点难,所以 Ocean 希望你帮他解决下面的问题:

对所有 k[1,n]k \in [1, n],输出对应的 cntcnt 最小值。

输入格式

本题包含多组数据。

第一行包含一个整数 tt,代表测试用例的数量。

接下来,对于每个测试用例:

第一行给定一个整数 nn,代表排列的大小。

第二行包含 nn 个整数,为待排序的排列 aa

输出格式

对于所有的测试用例,输出一行 nn 个整数,其中第 ii 个整数为 k=ik = i 时的 cntcnt 最小值。

样例

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

对于第一组测试用例, 你将得到排列 [2,3,1,4,6,5][\, 2, 3, 1, 4, 6, 5 \,]

我们来看看 k=1k = 1 的情况:

你可以按照下面的一个例子,使用最少的操作次数 33,将排列变为升序:

[2,3,1,4,6,5][\, 2, 3, 1, 4, 6, 5 \,] 1\xrightarrow{\, 1 \,} [2,3,1,4,[\, 2, 3, 1, 4, 0\color{red}{0} ,6,5], 6, 5 \,] 2\xrightarrow{\, 2 \,} [2,3,[\, 2, 3, 4\color{green}{4} ,1,0,6,5], 1, 0, 6, 5 \,] 2\xrightarrow{\, 2 \,} [[\, 1\color{green}{1} ,2,3,4,0,6,5], 2, 3, 4, 0, 6, 5 \,] 2\xrightarrow{\, 2\,} [1,2,3,4,0,5,[\, 1, 2, 3, 4, 0, 5, 6\color{green}{6} ]\,]

其中,箭头上面的数字为操作的类型,显然,操作 22 被执行了 33 次。红色的为插入的元素,绿色的为移动的元素。

我们再来看看 k=2k = 2 的情况:

你可以按照下面的一个例子,使用最少的操作次数 22,将排列变为升序:

[2,3,1,4,6,5][\, 2, 3, 1, 4, 6, 5 \,] 1\xrightarrow{\, 1 \,} [2,3,1,4,6,[\, 2, 3, 1, 4, 6, 0\color{red}{0} ,5], 5\,] 2\xrightarrow{\, 2 \,} [2,3,1,4,0,5,[\, 2, 3, 1, 4, 0, 5, 6\color{green}{6} ]\,] 1\xrightarrow{\, 1 \,} [2,3,[\, 2, 3, 0\color{red}{0} ,1,4,0,5,6], 1, 4, 0, 5, 6 \,] 2\xrightarrow{\, 2 \,} [[\, 1\color{green}{1} ,2,3,0,4,0,5,6], 2, 3, 0, 4, 0, 5, 6\,]

你可以归纳证明,k2k \geq 2 的时候,上面的排序方式都是次数最小且正确的。

对于第二组测试用例,显然排列已经升序,所以无需操作,答案自然为 00

提示

1t5001 \leq t \leq 500

1n5001 \leq n \leq 500

1ain1 \leq a_i \leq n

保证所有测试用例的 nn 总和不超过 500500