此问题与问题 B 不同。在此问题中,您必须输出 最大 对于从 $$$0$$$ 到 $$$n-1$$$ 的每个整数 $$$x$$$,所有操作的前缀最小值总和至少花费 $$$x$$$。
给定一个长度为 $$$n$$$ 的数组 $$$a$$$,其元素满足 $$$\boldsymbol{0 \le a_i \le n}$$$。您可以执行以下操作 最多一次:
- 选择两个索引 $$$i$$$ 和 $$$j$$$ 使得 $$$i \lt j$$$。设置$$$a_i := a_i + a_j$$$。然后,设置$$$a_j = 0$$$。
让 成本 一次操作的 是$$$j-i$$$的值。不执行操作的成本为 $$$0$$$。
对于从 $$$0$$$ 到 $$$n-1$$$(含)的每个整数 $$$x$$$,输出 最大 成本为 $$$\min(a_1) + \min(a_1,a_2) + \ldots + \min(a_1, a_2, \ldots, a_n)$$$ 的可能值 至少 $$$x$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^6$$$) — $$$a$$$ 的长度。
以下行包含 $$$n$$$ 以空格分隔的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$) — 表示数组 $$$a$$$。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,在新行中输出 $$$n$$$ 个整数:第 $$$i$$$ 个整数表示成本至少为 $$$i-1$$$ 的所有操作的最大答案。
示例
输入复制
621 242 3 1 421 055 5 0 5 554 1 3 3 1107 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$$$。数组 $$$a$$$ 变为 $$$[4,4,3,0,1]$$$,其得分为 $$$11$$$。
- $$$x=3$$$:最优操作是$$$i=2$$$ 和$$$j=5$$$,其成本为$$$3$$$。数组 $$$a$$$ 变为 $$$[4,2,3,3,0]$$$,其得分为 $$$10$$$。
- $$$x=4$$$:最佳(也是唯一)操作是 $$$i=1$$$ 和 $$$j=5$$$,其成本为 $$$4$$$。数组 $$$a$$$ 变为 $$$[5,1,3,3,0]$$$,其得分为 $$$8$$$。