凯文和尼维克正在争夺“最佳凯文”的称号。他们的目标是通过 $$$n$$$ 比赛来确定获胜者。
第 $$$i$$$ 匹配可以是以下两种类型之一:
- 类型 1:Kevin 需要花费 $$$a_i$$$ 时间来击败 Nivek 并赢得比赛。如果凯文不花 $$$a_i$$$ 时间,尼维克将赢得比赛。
- Type 2: The outcome of this match depends on their historical records.如果截至本场比赛凯文的胜场数大于或等于尼维克的胜场数,则凯文获胜。否则,尼维克获胜。
Kevin 想知道他需要花费多少时间来确保他至少赢得 $$$k$$$ 场比赛。
输出 $$$k = 0, 1, \ldots, n$$$ 的答案。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 匹配数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \leq a_i \leq 10^9$$$)。
如果$$$a_i = -1$$$,则第 $$$i$$$ 场比赛属于类型 2。否则,第 $$$i$$$ 场比赛属于类型 1,$$$a_i$$$ 表示 Kevin 赢得这场比赛所需花费的时间。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$n + 1$$$ 整数。 The $$$i$$$-th integer represents the minimum amount of time to win at least $$$i-1$$$ matches.
示例
输入 #1
3 5 -1 -1 -1 -1 -1 5 3 2 5 4 1 5 100 -1 -1 -1 1
输出 #1
0 0 0 0 0 0 0 1 3 6 10 15 0 1 100 100 100 101
注意
在第一个测试用例中,所有比赛都是类型 2。Kevin 可以自动赢得所有比赛。
In the second test case, all matches are of Type 1. Kevin can choose matches in increasing order of $$$a_i$$$.
在第三个测试用例中:
- 如果凯文在 $$$1$$$ 比赛中花费 $$$a_1$$$ 时间,他可以赢得 $$$1, 2, 3, 4$$$ 比赛。
- 如果 Kevin 在 $$$5$$$ 比赛中花费 $$$a_5$$$ 时间,他可以赢得 $$$5$$$ 比赛。
- If Kevin spends $$$a_1$$$ time on match $$$1$$$ and $$$a_5$$$ time on match $$$5$$$, he can win all matches.