A15729. 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 > q$ or $t\leq q$ . Note that $b_i = 0$ when $i<1$ or $i>c$ , $\sum\limits_{i=s}^{t}b_i = 0$ when $s>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$ .

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$ .

For each test case, print a line containing a single integer — the answer modulo $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$ .