C2. Усиление героев (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Она отличается от простой только ограничениями на $$$n$$$ и $$$t$$$.

Есть колода из $$$n$$$ карт, каждая из которых характеризуется своей силой. Бывают карты двух видов:

  • карта героя, сила такой карты всегда равна $$$0$$$;
  • карта бонуса, сила такой карты всегда положительна.

Вы можете делать с колодой следующее:

  • взять карту сверху колоды;
  • если эта карта является картой бонуса, вы можете положить её на верх своей колоды с бонусами либо в сброс;
  • если эта карта является картой героя, то к его силе прибавляется сила верхней карты из вашей колоды с бонусами (если она не пуста), после этого герой добавляется к вашей армии, а использованный бонус уходит в сброс.

Ваша задача с помощью таких действий собрать армию с наибольшей суммарной силой.

Входные данные

Первая строка входных данных содержит единственное число $$$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$$$.

Выходные данные

Выведите $$$t$$$ чисел, каждое из которых является ответом на соответствующий набор входных данных — максимальную возможную суммарную силу армии, которой можно добиться.

Пример
Входные данные
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
Примечание

В первом примере можно взять бонусы $$$1$$$ и $$$2$$$. Обе карты героев получат по $$$3$$$ к силе. Если взять все бонусы, один из них останется неиспользованным.

Во втором примере карту героя сверху колоды невозможно усилить, а остальных можно усилить бонусами $$$2$$$ и $$$3$$$ и получить $$$6$$$ суммарной силы.

В четвёртом примере можно взять бонусы $$$1$$$, $$$2$$$, $$$3$$$, $$$5$$$ и пропустить бонус $$$6$$$, тогда герой $$$4$$$ будет усилен бонусом $$$3$$$ на $$$5$$$, а герой $$$7$$$ бонусом $$$5$$$ на $$$4$$$. $$$4+5=9$$$.