解题思路

记 $N_k$ 为“包含 $0,1,\ldots,k-1$ 全部元素的连续片段个数”。某个片段的空号若为 $m$ ，则它对 $k=1,2,\ldots,m$ 各贡献 1，因此

\sum \mathrm{vac} = \sum_{k=1}^{n} N_k.

最大化空号之和，等价于对每个 $k$ 最大化 $N_k$ 。设 $0,1,\ldots,k-1$ 所在下标区间为 $[L_k,R_k]$ （下标从 1 到 $n$ ），则覆盖该区间的片段数为 $N_k = L_k \cdot (n-R_k+1)$ 。

题目内容

要把编号 $0, 1, \ldots, n-1$ 各使用一次，排成长度为 $n$ 的序列 $a$ 。对任意连续片段 $a_l, a_{l+1}, \ldots, a_r$ ，定义它的空号为该片段中未出现的最小非负整数。

请最大化所有连续片段的空号之和，即最大化 $\displaystyle \sum_{1 \le l \le r \le n} \mathrm{vac}(a_l, \ldots, a_r)$ ，其中 $\mathrm{vac}$ 表示空号。输出这个最大值，以及任意一个达到该最大值的序列。

空号：对非负整数构成的集合 $S$ ，空号是不在 $S$ 中的最小非负整数。例如 $S=\{1,2\}$ 时空号为 0， $S=\{0,1,3\}$ 时空号为 2。

约束：测试组数不超过 10^5，单组 $n$ 不超过 10^5，且所有测试中 $n$ 的总和不超过 2×10^5。