CF1827F.Copium Permutation

You are given a permutation $a_1,a_2,\ldots,a_n$ of the first $n$ positive integers. A subarray $[l,r]$ is called copium if we can rearrange it so that it becomes a sequence of consecutive integers, or more formally, if $$\max(a_l,a_{l+1},\ldots,a_r)-\min(a_l,a_{l+1},\ldots,a_r)=r-l$$ For each $k$ in the range $[0,n]$, print out the maximum number of copium subarrays of $a$ over all ways of rearranging the last $n-k$ elements of $a$.

给你一个 $1$ 到 $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 \in [0,n]$，输出：在所有将 $a$ 的后 $n-k$ 个元素重新排列的方式中，$a$ 所含 copium 子数组的最大可能数量。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$). It is guaranteed that the given numbers form a permutation of length $n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case print $n+1$ integers as the answers for each $k$ in the range $[0,n]$.

对于每个测试用例，输出 $n+1$ 个整数，分别表示 $k$ 在范围 $[0,n]$ 内时的每个答案。

In the first test case, the answer permutations for each $k$ are $[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]$.

In the second test case, the answer permutations for each $k$ are $[1,2,3,4]$, $[2,1,3,4]$, $[2,1,3,4]$, $[2,1,4,3]$, $[2,1,4,3]$.

在第一个测试用例中，每个 $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]$。