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

Maximise Sum

Examples