P15868 [MX-X26-T4] "Cfz Round 7" breakfast

An unending dream, an unbearable reality. They will both eventually turn into ordinary scenery.

Yuki has a sequence $a$ of length $n$. For the sequence $a$, Yuki defines its "Yuyu value" as: $$ \sum_{i=1}^n \operatorname{mex}(\{a_1,\dots,a_i\}) $$ That is, the sum of $\operatorname{mex}$ over all non-empty prefixes of $a$. Yuki defines one "bigger" operation as: - Choose a positive integer $i$ not greater than $n$ and a non-negative integer $v$, and change the value of $a_i$ to $a_i+v$. For each non-negative integer $k$ not greater than $n$, you need to find: if Yuki performs exactly $k$ "bigger" operations, what is the maximum possible "Yuyu value" of the sequence $a$. In this problem, the $\operatorname{mex}$ of a sequence is the smallest non-negative integer that does not appear in the sequence. For example: - $\operatorname{mex}(\{1,2,3\})=0$; - $\operatorname{mex}(\{0\})=1$; - $\operatorname{mex}(\{1,0,2,4\})=3$; In particular, when the sequence is empty, its $\operatorname{mex}$ is $0$.

**This problem contains multiple test cases.** The first line contains two integers $c,t$, representing the subtask ID of this test point and the number of test cases. The sample satisfies $c=0$. Then each test case is given as follows: - The first line contains an integer $n$. - The second line contains $n$ integers $a_1,\dots,a_n$.

For each test case, output one line containing $n+1$ integers. The $(k+1)$-th integer means the maximum "Yuyu value" that the sequence $a$ can achieve if Yuki performs exactly $k$ "bigger" operations.

### Sample 1 Explanation For the $1$-st test case: - When $k=0$, the "Yuyu value" of the sequence $a$ is $0+1+1+1=3$. - When $k=1$, you can change $a_3$ to $1$. Then the "Yuyu value" is $0+1+3+3=7$. For the $2$-nd test case: - When $k=0$, the "Yuyu value" of the sequence $a$ is $1+2+2+3+3=11$. - When $k=1$, you can change $a_3$ to $3$. Then the "Yuyu value" is $1+2+2+4+5=14$. - When $k=2$, you can change $a_3$ and $a_4$ to $2$ and $3$ respectively. Then the "Yuyu value" is $1+2+3+4+5=15$. ### Constraints Let $\sum n$ be the sum of $n$ within a single test point, and $\sum n^3$ be the sum of $n^3$ within a single test point. For all testdata: - $1 \le t \le 10^5$; - $1 \le n \le 500$, $\sum n^3 \le 500^3$; - For all $1\le i \le n$, $0 \le a_i \le 10^9$. **This problem uses bundled evaluation.** - Subtask 1 (13 points): $n \le 5$, $\sum n \le 20$. - Subtask 2 (17 points): $n \le 16$, $\sum n \le 20$. - Subtask 3 (27 points): $n \le 100$, $\sum n^3 \le 100^3$. - Subtask 4 (7 points): The sequence $a$ is a permutation of $0$ to $n-1$. - Subtask 5 (15 points): The sequence $a$ is non-decreasing. - Subtask 6 (21 points): No special constraints. Translated by ChatGPT 5