This problem differs from problem B. In this problem, you must output the maximum sum of prefix minimums over all operations that cost at least $x$ for each integer $x$ from $0$ to $n-1$.

You are given an array $a$ of length $n$, with elements satisfying $\boldsymbol{0 \le a_i \le n}$. You can perform the following operation at most once:

• Choose two indices $i$ and $j$ such that $i \lt j$. Set $a_i := a_i + a_j$. Then, set $a_j = 0$.

Let the cost of one operation be the value of $j-i$. The cost of not performing an operation is $0$.

For each integer $x$ from $0$ to $n-1$ inclusive, output the maximum possible value of $\min(a_1) + \min(a_1,a_2) + \ldots + \min(a_1, a_2, \ldots, a_n)$ over all possible operations that have a cost of at least $x$.

Input

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 an integer $n$ ($2 \leq n \leq 10^6$) — the length of $a$.

The following line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le n$) — denoting the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output $n$ integers on a new line: the $i$-th integer denoting the maximum answer over all operations that have a cost of at least $i-1$.

Note

Let's analyze the fifth test case:

• $x=0,1,2$: the optimal operation is $i=2$ and $j=4$, which has a cost of $2$. The array $a$ becomes $[4,4,3,0,1]$, which has a score of $11$.
• $x=3$: the optimal operation is $i=2$ and $j=5$, which has a cost of $3$. The array $a$ becomes $[4,2,3,3,0]$, which has a score of $10$.
• $x=4$: the optimal (and only) operation is $i=1$ and $j=5$, which has a cost of $4$. The array $a$ becomes $[5,1,3,3,0]$, which has a score of $8$.