G. Maximise Sum
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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

Example
Input
6
2
1 2
4
2 3 1 4
2
1 0
5
5 5 0 5 5
5
4 1 3 3 1
10
7 4 7 0 8 7 5 0 2 1
Output
3 3 
10 10 10 10 
1 1 
20 20 20 15 15 
11 11 11 10 8 
27 27 27 27 23 23 20 19 17 16
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$$$.