您将获得前 $$$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]$$$。