#P6. 【USTCPC2024】D. 坎坷之路
【USTCPC2024】D. 坎坷之路
小仓鼠李华在幼儿园就读期间跋涉坎坷之路,攀登崎岖之峰,以不屈之志与坚韧之心,跨越山海,终见曙光,最后凭借满 GPA 与数篇《超自然》杂志文章,获小仓鼠幼儿园“优秀学生奖学金-下界合金奖”。
因此,它打算用积木搭几条起伏的道路,以体现自己一路艰辛。这些积木路将在一块平地(初始平地上没有任何积木)上搭建,对于每条积木路:
长度为 格,第 格需要放置 块积木(即目标高度)。积木的搭建遵循以下规则:第 次可以选取一个合法区间 ,以消耗体力 的代价,在区间上的每格放置 1 块积木。一个区间合法,当且仅当区间中每格的高度相同,且都小于目标高度。
李华作为脑力工作者,不想消耗太多体力,所以请你帮它求出:为了搭出每条积木路,最小的体力总消耗值。由于结果可能很大,请输出对 998244353 取模后的值。
Input
输入第一行:一个整数 (),表示想搭的积木路条数。
接下来 行:对于条积木路,第一行为一个正整数 (),表示积木路的长度(格数);第二行为 个正整数 (),表示第 格的目标高度。
Output
输出 行:每行一个整数,表示搭每条积木路所需的最小体力消耗(对 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: