题目描述

这是该问题的困难版本。它与简单版本的区别仅在于 $n$ 和 $t$ 的约束条件不同。

有一副包含 $n$ 张牌的牌堆，每张牌都有一个力量值。牌分为两种类型：

• 英雄牌，这种牌的力量值总是等于 $0$；
• 奖励牌，这种牌的力量值总是正数。

你可以对牌堆进行如下操作：

• 从牌堆顶取出一张牌；
• 如果这张牌是奖励牌，你可以将它放到你的奖励牌堆顶，或者直接弃掉；
• 如果这张牌是英雄牌，那么你可以将你的奖励牌堆顶的奖励牌的力量值加到该英雄的力量上（如果奖励牌堆不为空），之后该英雄加入你的军队，并且用过的奖励牌被弃掉。

你的任务是通过这些操作，使你组建的军队的总力量尽可能大。

输入格式

输入的第一行为一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行为一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示牌堆中的牌数。

每个测试用例的第二行为 $n$ 个整数 $s_1, s_2, \dots, s_n$（$0 \le s_i \le 10^9$），表示从牌堆顶到底每张牌的力量值。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

输出 $t$ 行，每行一个数，表示对应测试用例下你能获得的军队最大总力量。

说明/提示

在第一个样例中，你可以拿奖励牌 $1$ 和 $2$。两个英雄牌都能获得 $3$ 的力量。如果你拿了所有奖励牌，其中一个奖励牌会被浪费。

在第二个样例中，牌堆顶的英雄牌无法获得加成，剩下的英雄牌可以分别用奖励牌 $2$ 和 $3$ 增强，总共获得 $6$ 的力量。

在第四个样例中，你可以拿奖励牌 $1$、$2$、$3$、$5$，跳过奖励牌 $6$，那么英雄牌 $4$ 会被奖励牌 $3$ 增强 $5$，英雄牌 $7$ 会被奖励牌 $5$ 增强 $4$，$4+5=9$。

由 ChatGPT 4.1 翻译

样例

5
5
3 3 3 0 0
6
0 3 3 0 0 3
7
1 2 3 0 4 5 0
7
1 2 5 0 4 3 0
5
3 1 0 0 4

6
6
8
9
4