G. 最大化总和
时间限制：4 秒
内存限制：512 兆字节

本题与问题 B 不同。本题中，你需要对每个 $x$ 从 $0$ 到 $n-1$，输出在所有代价至少为 $x$ 的操作中，前缀最小值之和的最大值。

给定一个长度为 $n$ 的数组 $a$，元素满足 $0 \le a_i \le n$。你可以执行至多一次如下操作：

• 选择两个下标 $i$ 和 $j$ 满足 $i < j$。令 $a_i := a_i + a_j$，然后令 $a_j = 0$。

一次操作的代价定义为 $j - i$。不执行操作的代价为 $0$。

对于每个整数 $x$ 从 $0$ 到 $n-1$ 包含，输出在所有代价至少为 $x$ 的操作中，

$$\min(a_1) + \min(a_1, a_2) + \dots + \min(a_1, a_2, \dots, a_n) $$

的最大值。

---

输入
每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^6$）—— 数组 $a$ 的长度。

第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le n$）—— 数组 $a$。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

---

输出
对于每个测试用例，输出一行 $n$ 个整数：第 $i$ 个整数表示在所有代价至少为 $i-1$ 的操作中，前缀最小值之和的最大值。

---

样例
输入

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

输出

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 

---

说明
分析第五个测试用例：

• $x = 0,1,2$：最优操作是 $i=2, j=4$，代价为 $2$，数组变为 $[4,4,3,0,1]$，得分为 $11$。
• $x = 3$：最优操作是 $i=2, j=5$，代价为 $3$，数组变为 $[4,2,3,3,0]$，得分为 $10$。
• $x = 4$：唯一操作是 $i=1, j=5$，代价为 $4$，数组变为 $[5,1,3,3,0]$，得分为 $8$。