B. Кризис на планете Шелезяка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Полезных ископаемых нет. Воды нет. Растительности нет. Населена роботами.

День на планете Шелезяка длится $$$n$$$ часов. Каждый робот, обитающий на этой планете, очень трудолюбивый. За день он по порядку перетаскивает $$$n$$$ ящиков массой $$$a_1, a_2, \ldots, a_n$$$, по ящику в час. Затем наступает следующий день, и он снова перетаскивает ящики массой $$$a_1, a_2, \ldots, a_n$$$. Ровно один раз в день между перетаскиваниями ящиков робот получает порцию смазки.

Механизмы роботов очень чувствительны, поэтому каждый перетащенный ящик наносит роботу урон. Ящик с номером $$$i$$$ моментально нанесёт $$$a_i$$$ урона за каждый час, начиная с $$$i$$$ до следующего получения смазки. Обратите внимание, что смазка может быть получена на следующий день.

Например, если $$$n = 8$$$, а мы выдали роботам смазку после перетаскивания $$$5$$$-го ящика:

  • Ящик $$$a_5$$$ нанесёт урон один раз (всего $$$a_5$$$ урона);
  • Ящик $$$a_6$$$ нанесёт урон восемь раз (всего $$$a_6 \cdot 8$$$ урона);
  • Ящик $$$a_2$$$ нанесёт урон четыре раза (всего $$$a_2 \cdot 4$$$ урона).

Вы можете выбрать момент, в который робот будет получать порцию смазки каждый день. Посчитайте минимальный урон, который будет нанесён роботу за один день при оптимальном выборе этого момента.

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

В первой строке вводится целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Далее следует описание наборов.

В первой строке каждого набора вводится целое число $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — количество перетаскиваний ящиков.

Во второй строке каждого набора вводится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^7$$$) — массы ящиков.

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

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

Для каждого набора входных данных выведите минимальный урон, который может получить робот за один день.

Пример
Входные данные
3
5
3 8 1 7 4
4
2 3 1 4
6
3 6 1 7 2 6
Выходные данные
59
23
79
Примечание

Разберём первый набор входных данных:

Если выдать смазку перед первым ящиком, $$$a_1$$$ урона нанесётся пять раз, $$$a_2$$$ урона нанесётся четыре раза и т.д., то есть суммарный урон будет равен: $$$5 \cdot a_1 + 4 \cdot a_2 + 3 \cdot a_3 + 2 \cdot a_4 + 1 \cdot a_5 = 15 + 32 + 3 + 14 + 4 = 68$$$.

Если выдать смазку после первого ящика, суммарный урон будет равен: $$$1 \cdot a_1 + 5 \cdot a_2 + 4\cdot a_3 + 3 \cdot a_4 + 2\cdot a_5 = 3 + 40 + 4 + 21 + 8 = 76$$$.

Если выдать смазку после второго ящика, суммарный урон будет равен: $$$6 + 8 + 5 + 28 + 12 = 59$$$.

После третьего ящика: $$$9 + 16 + 1 + 35 + 16 = 77$$$.

После четвёртого ящика: $$$12 + 24 + 2 + 7 + 20 = 65$$$.

Выдача смазки после пятого ящика эквивалентна выдаче смазки перед первым ящиком.

Таким образом, минимальный урон равен $$$59$$$.