← 返回题目列表

Codeforces · 1787/I

I. 寻宝

中文机器翻译题面 查看原题

定义序列 $$$b_1,b_2,\ldots,b_c$$$ 的美度值为 $$$\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i$$$ 的最大值,其中 $$$q$$$、$$$s$$$、$$$t$$$ 均为整数和 $$$s > q$$$ 或 $$$t\leq q$$$。请注意,当 $$$i<1$$$ 或 $$$i>c$$$ 时,$$$b_i = 0$$$;当 $$$s>t$$$ 时,$$$\sum\limits_{i=s}^{t}b_i = 0$$$。

例如,当$$$b = [-1,-2,-3]$$$时,我们可能有$$$q = 0$$$,$$$s = 3$$$,$$$t = 2$$$,因此美丽值为$$$0 + 0 = 0$$$。当$$$b = [-1,2,-3]$$$时,我们有$$$q = s = t = 2$$$,所以美丽值是$$$1 + 2 = 3$$$。

给定一个长度为$$$n$$$的序列$$$a$$$,确定序列$$$a$$$的所有非空子段$$$a_l,a_{l+1},\ldots,a_r$$$ ($$$1\leq l\leq r\leq n$$$)的美感值之和。

打印以 $$$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$$$) — 给定序列。

保证$$$n$$$的总和不超过$$$10^6$$$。

输出

对于每个测试用例,打印一行包含单个整数 - 答案模 $$$998\,244\,353$$$。

示例

输入 #1

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

输出 #1

5924
2548
148
98887

注意

在第二个测试用例中,对于子序列$$$[-26,43,-41,34,13]$$$,当$$$q=5$$$、$$$s=2$$$、$$$t=5$$$、$$$\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 23 + 49 = 72$$$。

在第三个测试用例中,只有一个非空连续子序列$$$[74]$$$。当$$$q=1$$$、$$$s=1$$$、$$$t=1$$$、$$$\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 148$$$。