Treasure Hunt
Contest: TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 3400
Tags: 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$$$.

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

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

Example input:
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

Example output:
5924
2548
148
98887

Editorial:
First, we observe that: $$$\max\limits_{l>p\,\texttt{or}\,r\leq p}{(\sum\limits_{i=1}^{p}{a_i}+\sum\limits_{i=l}^{r}{a_i})}=\max\limits_{p=1}^{n}{\sum\limits_{i=1}^{p}{a_i}}+\max\limits_{l,r}{\sum\limits_{i=l}^{r}{a_i}}$$$.
Proof: We can proof it by contradiction. Define $$$g(l,r,p)$$$ as $$$\sum\limits_{i=1}^{p}{a_i}+\sum\limits_{i=l}^{r}{a_i}$$$. Suppose $$$l\leq p<r$$$ when $$$g(l,r,p)$$$ hits the maximum value. If $$$\sum\limits_{i=p+1}^{r}{a_i}\geq 0$$$, $$$g(l,r,r)\geq g(l,r,p)$$$, otherwise $$$g(l,p,p)> g(l,r,p)$$$. So the above observation is always correct.
So we can divide the problem into two parts: $$$\max\limits_{p=1}^{n}{\sum\limits_{i=1}^{p}{a_i}}$$$ and $$$\max\limits_{l,r}{\sum\limits_{i=l}^{r}{a_i}}$$$.
For $$$\max\limits_{p=1}^{n}{\sum\limits_{i=1}^{p}{a_i}}$$$, it's easy to solve it by using a stack to calculate the prefix maximum value, and then calculate the answer.
And for $$$\max\limits_{l,r}{\sum\limits_{i=l}^{r}{a_i}}$$$, consider divide and conquer. For a part $$$[l,r]$$$,let $$$m=\lfloor \frac{l+r}{2}\rfloor$$$. Define $$$h(L,R)$$$ as $$$\max\limits_{L\leq l,r\leq R}{\sum\limits_{i=l}^{r}{a_i}}$$$. We want to calculate the sum of $$$h(L,R)$$$ satisfied $$$l\leq L\leq m<R < r$$$. Obviously $$$h(L,R) = \max(\max(h(L,m),h(m+1,R)),\max\limits_{L\leq p\leq m}{\sum\limits_{j=p}^{m}{a_j}}+\max\limits_{m<p\leq R}{\sum\limits_{j=m+1}^{p}{a_j}})$$$, and it's easy to calculate above four value in the time complexity of $$$O(r - l)$$$. We can use binary search to calculate the maximum value. So the problem can be solved in the time complexity of $$$O(n\log ^2n)$$$.
But it's not good enough. We can solve it in the time complexity of $$$O(n\log n)$$$ based on the following theorem:
Define $$$f(p)$$$ as $$$\max\limits_{1\leq q\leq p}{\sum\limits_{i=1}^q{a_i}}$$$. $$$h(1,p)-f(p)$$$ is non-decreasing.
Proof: Actually, if we extend the first theorem, we will find $$$l>p$$$ or $$$r=p$$$ :
If $$$l>p$$$, so $$$\sum\limits_{i=p+1}^r{a_i}<0$$$. When we add an element at the back of the sequence: If $$$\sum\limits_{i=1}^{len}{a_i}>\sum\limits_{i=1}^p{a_i}$$$, $$$p$$$ and $$$r$$$ become $$$len$$$ at the same time. So $$$\Delta f(len)<\Delta h(1,len)$$$ since $$$\sum\limits_{i=p+1}^r{a_i}<0$$$. Otherwise if $$$\sum\limits_{i=1}^{len}{a_i}\leq \sum\limits_{i=1}^p{a_i}$$$, $$$\Delta f(len)=0$$$ while $$$\Delta h(1,len) \geq 0$$$. So the theorem always holds in this circumstance.
If $$$p=r$$$, $$$\Delta f(len)=\Delta h(1,len)$$$, so the theorem holds too.
Because of the theorem, we can replace binary search by two pointers. So the final time complexity is $$$O(n\log n)$$$.