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 > q $ or $ t\leq q $ . Note that $ b_i = 0 $ when $ ic $ , $ \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 $ .