A. Отличные графы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Фермера Джона есть ферма, состоящая из $$$n$$$ пастбищ, соединенных с помощью односторонних дорог. У каждой дороги есть вес, означающий время, которое необходимо потратить, чтобы пройти по ней. Дороги могут иметь отрицательный вес, иными словами, коровы по ним движутся так быстро, что способны перемещаться назад во времени! Однако, Фермер Джон гарантирует, что коровы никак не смогут попасть во временную петлю в том смысле, что не смогут, двигаясь по дорогам, уйти бесконечно далеко в прошлое. Кроме того, каждая пара пастбищ соединена не более чем одной дорогой в каждом направлении.

К сожалению, Фермер Джон потерял карту фермы. Все, что он знает — это массив $$$d$$$, где $$$d_i$$$ — это минимальное время, за которое коровы могут добраться до $$$i$$$-го пастбища из $$$1$$$-го, двигаясь по дорогам. Стоимость его фермы — это сумма весов всех дорог, и Фермер Джон хочет узнать минимально возможную стоимость фермы, которая не противоречит тому, что он помнит.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

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

Во второй строке каждого набора заданы $$$n$$$ целых чисел через пробел $$$d_1, d_2, \ldots, d_n$$$ ($$$0 \leq d_i \leq 10^9$$$) — массив $$$d$$$. Гарантируется, что $$$d_1 = 0$$$.

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

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

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

Пример
Входные данные
3
3
0 2 3
2
0 1000000000
1
0
Выходные данные
-3
0
0
Примечание

В первом наборе вы можете добавить дороги

  • от пастбища $$$1$$$ к пастбищу $$$2$$$ с весом $$$2$$$,
  • от пастбища $$$2$$$ к пастбищу $$$3$$$ с весом $$$1$$$,
  • от пастбища $$$3$$$ к пастбищу $$$1$$$ с весом $$$-3$$$,
  • от пастбища $$$3$$$ к пастбищу $$$2$$$ с весом $$$-1$$$,
  • от пастбища $$$2$$$ к пастбищу $$$1$$$ с весом $$$-2$$$.
Суммарная стоимость равна $$$2 + 1 + -3 + -1 + -2 = -3$$$.

Во втором набор вы можете добавить дорогу от пастбища $$$1$$$ к пастбищу $$$2$$$ с весом $$$1000000000$$$ и дорогу от пастбища $$$2$$$ к пастбищу $$$1$$$ со стоимостью $$$-1000000000$$$. Суммарная стоимость равна $$$1000000000 + -1000000000 = 0$$$.

В третьем наборе, вы не можете добавить ни одной дороги. Суммарная стоимость равна $$$0$$$.