CF1787I Treasure Hunt

定义序列 $b_1,b_2,\ldots,b_c$ 的 beauty 值为 $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i$ 的最大值，其中 $q,s,t$ 均为非负整数，且 $s>q$ 或 $t\le q$。注意当 $ic$ 时 $b_i = 0$；当 $s>t$ 时 $\sum\limits_{i=s}^t b_i = 0$。 例如，$b = [-1,-2,-3]$ 时，beauty 值为 $0 + 0 = 0$，此时一组可行的 $q,s,t$ 为 $q = 0,s = 3,t = 2$。$b = [-1,2,-3]$ 时，beauty 值为 $1 + 2 = 3$，此时一组可行的 $q,s,t$ 为 $q = s = t = 2$。 给出长度为 $n$ 的序列 $a$，求出 $a$ 的所有非空子段 $a_l,a_{l+1},\ldots,a_r$（$1\leq l\leq r\leq n$）的 beauty 值之和。 输出对 $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$）表示序列 $a$。

对于每组测试数据输出一行一个正整数表示答案模 $998\,244\,353$ 的值。 ### 样例解释 第二组测试数据中，对于子段 $[-26,43,-41,34,13]$，beauty 值为 $\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 23 + 49 = 72$，此时 $q=5$，$s=2$，$t=5$。 第三组测试数据中，只有一个子段 $[74]$，beauty 值为 $148$，此时 $q = s = t = 1$。

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