CF1787I.Treasure Hunt

Define the beauty value of a sequence $b_1,b_2,\ldots,b_c$ as the maximum value of $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i$, where $q$, $s$, $t$ are all integers and $s \gt q$ or $t\leq q$. Note that $b_i = 0$ when $i \lt 1$ or $i \gt c$, $\sum\limits_{i=s}^{t}b_i = 0$ when $s \gt t$.

For example, when $b = [-1,-2,-3]$, we may have $q = 0$, $s = 3$, $t = 2$ so the beauty value is $0 + 0 = 0$. And when $b = [-1,2,-3]$, we have $q = s = t = 2$ so the beauty value is $1 + 2 = 3$.

You are given a sequence $a$ of length $n$, determine the sum of the beauty value of all non-empty subsegments $a_l,a_{l+1},\ldots,a_r$ ($1\leq l\leq r\leq n$) of the sequence $a$.

Print the answer modulo $998\,244\,353$.

定义序列 $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$。注意：当 $i < 1$ 或 $i > c$ 时，$b_i = 0$；当 $s > t$ 时，$\sum\limits_{i=s}^{t}b_i = 0$。

例如，当 $b = [-1,-2,-3]$ 时，可取 $q = 0$、$s = 3$、$t = 2$，此时美观值为 $0 + 0 = 0$；当 $b = [-1,2,-3]$ 时，可取 $q = s = t = 2$，此时美观值为 $1 + 2 = 3$。

给定一个长度为 $n$ 的序列 $a$，请计算序列 $a$ 的所有非空子段 $a_l,a_{l+1},\ldots,a_r$（其中 $1 \leq l \leq r \leq n$）的美观值之和。

输出答案对 $998\,244\,353$ 取模的结果。

Each test contains multiple test cases. The first line contains an integer $T$ ($1 \le T \le 10^4$) — the number of test cases.

The first line contains an integer $n$ ($1\le n\le 10^6$) — the length of $a$.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-10^6 \leq a_i \leq 10^6$) — the given sequence.

It's guaranteed that the sum of $n$ does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, print a line containing a single integer — the answer modulo $998\,244\,353$.

对于每个测试用例，输出一行，包含一个整数——答案对 $998\,244\,353$ 取模的结果。

In the second test case, for the subsequence $[-26,43,-41,34,13]$, when $q=5$, $s=2$, $t=5$, $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 23 + 49 = 72$.

In the third test case, there is only one non-empty consecutive subsequence $[74]$. When $q=1$, $s=1$, $t=1$, $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 148$.

在第二个测试用例中，对于子序列 $[-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$。