C. Кошмар Теофаниса
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Теофанис легко зацикливается на задачах перед сном, и они часто снятся ему в кошмарах. Чтобы справиться с этим, он обратился к своему врачу, доктору Эмиксу.

В последнем кошмаре у него был массив $$$a$$$ длины $$$n$$$, и он хотел разбить его на непустые подмассивы$$$^{\dagger}$$$ так, чтобы каждый элемент находился ровно в одном из подмассивов.

Например, массив $$$[1,-3,7,-6,2,5]$$$ можно разбить на $$$[1] [-3,7] [-6,2] [5]$$$.

Киприотское значение такого разбиения равняется $$$\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i$$$, где $$$k$$$ — количество подмассивов, на которое мы разделили массив, а $$$\mathrm{sum}_i$$$ — сумма $$$i$$$-го подмассива.

Киприотское значение разбиения массива $$$[1] [-3,7] [-6,2] [5] = 1 \cdot 1 + 2 \cdot (-3 + 7) + 3 \cdot (-6 + 2) + 4 \cdot 5 = 17$$$.

Теофанису интересно, каково максимальное киприотское значение среди всех разбиений массива.

$$$^{\dagger}$$$ Массив $$$b$$$ является подмассивом массива $$$a$$$, если $$$b$$$ может быть получен из $$$a$$$ удалением нескольких (возможно, нуля или всех) элементов из начала и нескольких (возможно, нуля или всех) элементов из конца. В частности, массив является подмассивом самого себя.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — размер массива.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^8 \le a_i \le 10^{8}$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^{5}$$$.

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

Для каждого набора входных данных выведите одно целое число — максимальное киприотское значение среди всех разбиений массива $$$a$$$.

Пример
Входные данные
4
6
1 -3 7 -6 2 5
4
2 9 -5 -3
8
-3 -4 2 -5 1 10 17 23
1
830
Выходные данные
32
4
343
830
Примечание

В первом наборе входных данных для получения максимального киприотского значения мы разобьём массив на $$$[1][-3][7][-6][2][5]$$$, что даст нам: $$$\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i = 1 \cdot 1 + 2 \cdot (-3) + 3 \cdot 7 + 4 \cdot (-6) + 5 \cdot 2 + 6 \cdot 5 = 32$$$.

Аналогично, во втором наборе входных данных мы разбиваем массив на $$$[2][9,-5,-3]$$$, что дает нам $$$\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i = 1 \cdot 2 + 2 \cdot (9 + (-5) + (-3)) = 4$$$.