CF1800C2.Powering the Hero (hard version)

This is a hard version of the problem. It differs from the easy one only by constraints on $n$ and $t$.

There is a deck of $n$ cards, each of which is characterized by its power. There are two types of cards:

• a hero card, the power of such a card is always equal to $0$;
• a bonus card, the power of such a card is always positive.

You can do the following with the deck:

• take a card from the top of the deck;
• if this card is a bonus card, you can put it on top of your bonus deck or discard;
• if this card is a hero card, then the power of the top card from your bonus deck is added to his power (if it is not empty), after that the hero is added to your army, and the used bonus discards.

Your task is to use such actions to gather an army with the maximum possible total power.

这是一个该问题的困难版本，与简单版本的唯一区别在于对 $n$ 和 $t$ 的约束条件。

有一副包含 $n$ 张卡牌的牌堆，每张牌均具有一个“力量值”。卡牌分为两类：

• 英雄牌：其力量值恒为 $0$；
• 增益牌：其力量值恒为正数。

你可对牌堆执行以下操作：

• 从牌堆顶部取出一张牌；
• 若该牌为增益牌，则你可以将其置于你的增益牌堆顶部，或直接弃掉；
• 若该牌为英雄牌，则（若你的增益牌堆非空）将增益牌堆顶部那张牌的力量值加到该英雄牌的力量值上；随后，将该英雄牌加入你的军队，且已使用的那张增益牌被弃掉。

你的任务是通过上述操作，组建一支总力量值尽可能大的军队。

The first line of input data contains single integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of cards in the deck.

The second line of each test case contains $n$ integers $s_1, s_2, \dots, s_n$ ($0 \le s_i \le 10^9$) — card powers in top-down order.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

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

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 表示牌组中卡片的数量。

每个测试用例的第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$（$0 \le s_i \le 10^9$）—— 表示从上到下的各张卡片的点数。

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

Output $t$ numbers, each of which is the answer to the corresponding test case — the maximum possible total power of the army that can be achieved.

输出 $t$ 个数字，每个数字对应一个测试用例的答案——即所能达到的军队总战力的最大值。

In the first sample, you can take bonuses $1$ and $2$. Both hero cards will receive $3$ power. If you take all the bonuses, one of them will remain unused.

In the second sample, the hero's card on top of the deck cannot be powered up, and the rest can be powered up with $2$ and $3$ bonuses and get $6$ total power.

In the fourth sample, you can take bonuses $1$, $2$, $3$, $5$ and skip the bonus $6$, then the hero $4$ will be enhanced with a bonus $3$ by $5$, and the hero $7$ with a bonus $5$ by $4$. $4+5=9$.

在第一个样例中，你可以选择奖励 $1$ 和 $2$。两张英雄卡都将获得 $3$ 点力量值。若你选择全部奖励，则其中有一个奖励将无法使用。

在第二个样例中，牌堆顶部的英雄卡无法被增强，其余英雄卡可分别用奖励 $2$ 和 $3$ 进行增强，总共获得 $6$ 点力量值。

在第四个样例中，你可以选择奖励 $1$、$2$、$3$、$5$，跳过奖励 $6$；此时英雄 $4$ 将通过奖励 $3$ 获得 $5$ 点力量值增强，英雄 $7$ 将通过奖励 $5$ 获得 $4$ 点力量值增强。$4+5=9$。