CF1827F Copium Permutation

给定一个长度为 $n$ 的排列 $a_1,a_2,\ldots,a_n$，排列包含了前 $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$，$k$ 的取值范围为 $[0,n]$，请输出将 $a$ 的最后 $n-k$ 个元素重新排列后，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$ 的排列。 保证所有测试数据中 $n$ 的总和不超过 $2\cdot 10^5$。

对于每组测试数据，输出 $n+1$ 个整数，分别表示对于每个 $k$（$k$ 取 $[0,n]$），将 $a$ 的最后 $n-k$ 个元素重新排列后，copium 子数组的最大数量。

在第一个测试点中，每个 $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]$。 由 ChatGPT 4.1 翻译