Background

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

Problem Description

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$.

Input Format

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$.

Output Format

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.

0 3
4
2 0 0 9
5
0 1 0 2 4
7
4 0 9 8 1 3 8

3 7 7 7 7
11 14 15 15 15 15
9 9 9 9 9 9 9 9

Hint

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