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

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел. Вы можете совершить следующую операцию любое число раз (0 или больше раз):

  • Выбрать $$$2$$$ индекса $$$i$$$,$$$j$$$ где $$$1 \le i < j \le n$$$ и заменить $$$a_k$$$ для всех $$$i \leq k \leq j$$$ значением $$$|a_i - a_j|$$$

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

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

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

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$.

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

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

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

Для каждого набора входных данных выведите сумму конечного массива.

Пример
Входные данные
3
3
1 1 1
2
9 1
3
4 9 5
Выходные данные
3
16
18
Примечание

В первом примере невозможно достичь сумму $$$> 3$$$ используя операцию, таким образом ответ $$$3$$$.

Во втором примере можно показать, что максимальная достижимая сумма равна $$$16$$$. Используем операцию $$$(1,2)$$$ и преврати массив из $$$[9,1]$$$ в $$$[8,8]$$$, таким образом ответ равен $$$16$$$.

В третьем примере можно показать, что невозможно достичь суммы $$$> 18$$$ используя операцию, таким образом ответ $$$18$$$.