G. Сумматоха
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Обратите внимание, что ответ в этой задаче может не поместиться в int64 или long long. Рекомендуется использовать int128.

Для массива $$$b$$$ длины $$$m$$$, определим $$$f(b)$$$ как минимальное возможное значение $$$\max(b) - \min(b)$$$, которого можно достичь применив следующую операцию любое число раз:

  • Выбрать любой индекс $$$1 \le i \lt m$$$, и сделать одно из двух действий:
    1. Присвоить $$$b_{i+1} := b_{i+1} + b_i$$$,
    2. Присвоить $$$b_{i+1} := b_{i+1} - b_i$$$.

Вам дан массив $$$a$$$ длины $$$n$$$. Ваша задача посчитать сумму $$$f$$$ по всем подмассивам$$$^{\text{∗}}$$$ $$$a$$$. Формально вам нужно найти значение

$$$$$$\sum_{1 \le l \le r \le n} f([a_l,a_{l+1},\dots,a_r]).$$$$$$

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

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

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

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

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

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

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

Для каждого набора входных данных выведите одно целое число — значение $$$\sum_{1 \le l \le r \le n} f([a_l,a_{l+1},\dots,a_r])$$$.

Пример
Входные данные
5
3
6 4 8
4
1 2 3 4
9
9 9 8 2 4 4 3 5 3
6
18 12 24 9 6 36
6
36 24 18 12 9 6
Выходные данные
4
3
39
72
111
Примечание

Рассмотрим все подмассивы в первом примере.

  • Для подмассивов из одного элемента $$$[6]$$$, $$$[4]$$$ и $$$[8]$$$ операции ничего не меняют, каждый из них добавит в сумму $$$0$$$.
  • Для $$$[6,4]$$$, первый элемент равен $$$6$$$ и не может измениться. Второй элемент может стать либо $$$4+6=10$$$ либо $$$4-6=-2$$$ и разность станет $$$4$$$ или $$$8$$$. Лучше не применять операцию, так что к сумме прибавится $$$2$$$.
  • Для $$$[4,8]$$$ выберем $$$i=1$$$ и присвоим $$$b_{2}:=b_{2}-b_{1}$$$. Тогда подмассив станет равен $$$[4,4]$$$ и к сумме прибавится $$$0$$$.
  • Для $$$[6,4,8]$$$, не будем менять значения первых двух элементов и выберем $$$i=2$$$, присвоим $$$b_{3}:=b_{3}-b_{2}$$$. Теперь $$$8$$$ превратилась в $$$4$$$, а массив равен $$$[6,4,4]$$$. Так что $$$\max(b)-\min(b)=6-4=2$$$, можно показать что это минимальное возможное значение.

Ответом для первого примера будет $$$0+0+0+2+0+2=4$$$.

Во втором примере подмассивы длины $$$1$$$ дают $$$0$$$. Среди остальных только $$$[2,3]$$$, $$$[3,4]$$$ и $$$[2,3,4]$$$ дают $$$1$$$, все оставшиеся дают ноль. Ответ равен $$$1+1+1=3$$$.