#P6. 【USTCPC2024】D. 坎坷之路

    ID: 160 Type: Default 2000ms 256MiB

【USTCPC2024】D. 坎坷之路

小仓鼠李华在幼儿园就读期间跋涉坎坷之路,攀登崎岖之峰,以不屈之志与坚韧之心,跨越山海,终见曙光,最后凭借满 GPA 与数篇《超自然》杂志文章,获小仓鼠幼儿园“优秀学生奖学金-下界合金奖”。

因此,它打算用积木搭几条起伏的道路,以体现自己一路艰辛。这些积木路将在一块平地(初始平地上没有任何积木)上搭建,对于每条积木路:

长度为 nn 格,第 ii 格需要放置 hih_i 块积木(即目标高度)。积木的搭建遵循以下规则:第 kk 次可以选取一个合法区间 [lk,rk][l_k,r_k],以消耗体力 k×(rklk+1)k \times (r_k - l_k + 1) 的代价,在区间上的每格放置 1 块积木。一个区间合法,当且仅当区间中每格的高度相同,且都小于目标高度

李华作为脑力工作者,不想消耗太多体力,所以请你帮它求出:为了搭出每条积木路,最小的体力总消耗值。由于结果可能很大,请输出对 998244353 取模后的值。

Input

输入第一行:一个整数 TT1T101 \le T \le 10),表示想搭的积木路条数。

接下来 2T2T 行:对于条积木路,第一行为一个正整数 nn1n106,1T×n3×1061\le n\le 10^6, 1\le T \times n\le 3 \times 10^6),表示积木路的长度(格数);第二行为 nn 个正整数 hih_i0hi1090 \le h_i\leq 10^9),表示第 ii 格的目标高度。

Output

输出 TT 行:每行一个整数,表示搭每条积木路所需的最小体力消耗(对 998244353 取模)。

Examples

Sample Input 1

3
10
8 9 9 9 7 6 6 6 4 3
10
2 10 9 8 6 10 5 4 3 2
10
9 0 10 10 1 9 8 1 7 7

Sample Output 1

278
265
843

Related

In following contests:

USTCPC2025 测试赛