对于 $$$n$$$ 整数的数组 $$$b$$$,该数组的极值是必须执行以下操作以使 $$$b$$$ 非递减的最小次数(可能为零):
- 选择索引 $$$i$$$,使得 $$$1 \le i \le |b|$$$,其中 $$$|b|$$$ 是 $$$b$$$ 的当前长度。
- 将 $$$b_i$$$ 替换为两个元素 $$$x$$$ 和 $$$y$$$,使得 $$$x$$$ 和 $$$y$$$ 都是正整数,并且 $$$x + y = b_i$$$。
- 这样,数组 $$$b$$$ 发生变化,并且下一个操作将在此修改后的数组上执行。
例如,如果 $$$b = [2, 4, 3]$$$ 且索引 $$$2$$$ 被选中,则此操作后可能的数组为 $$$[2, \underline{1}, \underline{3}, 3]$$$, $$$[2, \underline{2}, \underline{2}, 3]$$$ 或 $$$[2, \下划线{3},\下划线{1},3]$$$。因此,对于这个数组,这个单一操作就足以使其不减:$$$[2, 4, 3] \rightarrow [2, \underline{2}, \underline{2}, 3]$$$。
很容易看出,每个正整数数组都可以通过这种方式变得不减。
YouKn0wWho 有一个由 $$$n$$$ 整数组成的数组 $$$a$$$。帮助他求 $$$a$$$ 模 $$$998\,244\,353$$$ 的所有非空子数组的极值之和。如果一个子数组在$$$a$$$中出现多次,则其极值应按其出现的次数计算。
数组 $$$d$$$ 是数组 $$$c$$$ 的子数组,如果 $$$d$$$ 可以通过删除开头的几个(可能是零个或全部)元素和结尾的几个(可能是零个或全部)元素从 $$$c$$$ 获得。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印一个整数 - $$$a$$$ 模 $$$998\,244\,353$$$ 的所有子数组的极值之和。
示例
输入 #1
4 3 5 4 3 4 3 2 1 4 1 69 8 7264 40515 28226 92776 35285 21709 75124 48163
输出 #1
5 9 0 117
注意
令 $$$f(l, r)$$$ 表示 $$$[a_l, a_{l+1}, \ldots, a_r]$$$ 的极值。
在第一个测试用例中,
- $$$f(1, 3) = 3$$$,因为 YouKn0wWho 可以对子数组 $$$[5, 4, 3]$$$ 执行以下操作(新插入的元素带有下划线):$$$[5, 4, 3] \rightarrow [\underline{3}, \underline{2}, 4, 3] \rightarrow [3, 2, \下划线{2}, \下划线{2}, 3] \rightarrow [\下划线{1}, \下划线{2}, 2, 2, 2, 3]$$$;
- $$$f(1, 2) = 1$$$,因为 $$$[5, 4] \rightarrow [\underline{2}, \underline{3}, 4]$$$;
- $$$f(2, 3) = 1$$$,因为 $$$[4, 3] \rightarrow [\underline{1}, \underline{3}, 3]$$$;
- $$$f(1, 1) = f(2, 2) = f(3, 3) = 0$$$,因为它们已经是非递减的。
因此$$$a的所有子数组的极值总和 = 3 + 1 + 1 + 0 + 0 + 0 = 5$$$。