← 返回题目列表

Codeforces · 1827/F

F. Copium 排列

中文机器翻译题面 查看原题

您将获得前 $$$n$$$ 正整数的排列 $$$a_1,a_2,\ldots,a_n$$$。子数组 $$$[l,r]$$$ 被称为 copium,如果我们可以重新排列它,使其成为连续整数的序列,或者更正式地,如果 $$$$$$\max(a_l,a_{l+1},\ldots,a_r)-\min(a_l,a_{l+1},\ldots,a_r)=r-l$$$$$$ 对于范围内的每个 $$$k$$$ $$$[0,n]$$$,通过重新排列 $$$a$$$ 的最后 $$$n-k$$$ 元素的所有方式,打印出 $$$a$$$ 的 copium 子数组的最大数量。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)。保证给定的数字形成长度为 $$$n$$$ 的排列。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,打印 $$$n+1$$$ 整数作为 $$$[0,n]$$$ 范围内每个 $$$k$$$ 的答案。

示例

输入 #1

5
5
5 2 1 4 3
4
2 1 4 3
1
1
8
7 5 8 1 4 2 6 3
10
1 4 5 3 7 8 9 2 10 6

输出 #1

15 15 11 10 9 9 
10 8 8 7 7 
1 1 
36 30 25 19 15 13 12 9 9 
55 55 41 35 35 25 22 22 19 17 17

注意

在第一个测试用例中,每个 $$$k$$$ 的答案排列为 $$$[1,2,3,4,5]$$$, $$$[5,4,3,2,1]$$$, $$$[5,2,3,4,1]$$$, $$$[5,2,1,3,4]$$$, $$$[5,2,1,4,3]$$$,$$$[5,2,1,4,3]$$$。

在第二个测试用例中,每个 $$$k$$$ 的答案排列为 $$$[1,2,3,4]$$$、$$$[2,1,3,4]$$$、$$$[2,1,3,4]$$$、$$$[2,1,4,3]$$$、$$$[2,1,4,3]$$$。