I. Treasure Hunt
data structures; divide and conquer; two pointers
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\).