Kevin and Nivek - المسألة

Kevin 和 Nivek 正在争夺“最强 Kevin”的称号。他们旨在通过 $n$ 场比赛来决出胜者。第 $i$ 场比赛分为两种类型：

类型 1：Kevin 需要花费 $a_i$ 的时间来击败 Nivek 并赢得比赛。如果 Kevin 不在比赛上花费 $a_i$ 的时间，Nivek 将赢得比赛。
类型 2：比赛结果取决于他们之前的比赛记录。如果到目前为止 Kevin 的胜场数大于或等于 Nivek 的胜场数，则 Kevin 获胜。否则，Nivek 获胜。

Kevin 想知道他为了确保至少赢得 $k$ 场比赛所需要花费的最少时间。请输出对于 $k = 0, 1, \dots, n$ 的答案。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 3 \cdot 10^5$) —— 比赛场数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-1 \le a_i \le 10^9$)。

如果 $a_i = -1$，则第 $i$ 场比赛为类型 2。否则，第 $i$ 场比赛为类型 1，$a_i$ 表示 Kevin 赢得该场比赛所需花费的时间。

保证所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出 $n + 1$ 个整数。第 $i$ 个整数表示赢得至少 $i - 1$ 场比赛所需的最少时间。

3
5
-1 -1 -1 -1 -1
5
3 2 5 4 1
5
100 -1 -1 -1 1

0 0 0 0 0 0
0 1 3 6 10 15
0 1 100 100 100 101

在第一个测试用例中，所有比赛均为类型 2。Kevin 可以自动赢得所有比赛。

在第二个测试用例中，所有比赛均为类型 1。Kevin 可以按 $a_i$ 从小到大的顺序选择比赛。

在第三个测试用例中：

QOJ.ac