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

Определим значение красоты последовательности $$$b_1,b_2,\ldots,b_c$$$ как максимальное значение $$$\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i$$$, где $$$q$$$, $$$s$$$, $$$t$$$ являются целыми числами и $$$s > q$$$ или $$$t\leq q$$$. Обратите внимание, что $$$b_i = 0$$$, когда $$$i<1$$$ или $$$i>c$$$, $$$\sum\limits_{i=s}^{t}b_i = 0$$$, когда $$$s>t$$$.

Например, если $$$b = [-1,-2,-3]$$$, у нас может быть $$$q = 0$$$, $$$s = 3$$$, $$$t = 2$$$, поэтому значение красоты равно $$$0 + 0 = 0$$$. А если $$$b = [-1,2,-3]$$$ и $$$q = s = t = 2$$$, то значение красоты будет равно $$$1 + 2 = 3$$$.

Вам дана последовательность $$$a$$$ длины $$$n$$$, определите сумму красоты всех непустых подотрезков $$$a_l,a_{l+1},\ldots,a_r$$$ ($$$1\leq l\leq r\leq n$$$) последовательности $$$a$$$.

Выведите ответ по модулю $$$998\,244\,353$$$.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^6 \leq a_i \leq 10^6$$$) — заданная последовательность.

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

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

Для каждого набора входных данных выведите строку, содержащую одно целое число — ответ по модулю $$$998\,244\,353$$$.

Пример
Входные данные
4
7
80 59 100 -52 -86 -62 75
8
-48 -14 -26 43 -41 34 13 55
1
74
20
56 -60 62 13 88 -48 64 36 -10 19 94 25 -69 88 87 79 -70 74 -26 59
Выходные данные
5924
2548
148
98887
Примечание

Во втором наборе входных данных для подпоследовательности $$$[-26,43,-41,34,13]$$$, когда $$$q=5$$$, $$$s=2$$$, $$$t=5$$$, $$$\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 23 + 49 = 72$$$.

В третьем наборе входных данных имеется только одна непустая последовательная подпоследовательность $$$[74]$$$. Когда $$$q=1$$$, $$$s=1$$$, $$$t=1$$$, $$$\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 148$$$.