CF2061I 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, \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$ 个整数。第 $i$ 个整数表示至少赢得 $i-1$ 场比赛所需的最小时间。

第一个测试用例中，所有比赛均为类型 2。Kevin 可以自动赢得所有比赛。 第二个测试用例中，所有比赛均为类型 1。Kevin 可以按 $a_i$ 递增的顺序选择比赛。 第三个测试用例中： - 如果 Kevin 在第 1 场比赛花费 $a_1$ 时间，他可以赢得第 1、2、3、4 场比赛。 - 如果 Kevin 在第 5 场比赛花费 $a_5$ 时间，他可以赢得第 5 场比赛。 - 如果 Kevin 在第 1 场比赛花费 $a_1$ 时间并在第 5 场比赛花费 $a_5$ 时间，他可以赢得所有比赛。 翻译由 DeepSeek R1 完成