{"problem":{"name":"「SMOI-R1」Game","description":{"content":"在这个游戏里，一开始有 $n$ 个病毒，每个病毒的危害值为 $1$。 每隔一段时间，病毒就会变异，会分裂成两个病毒，右边的病毒会比左边的病毒危害值多 $1$，变异过的病毒不会再变异。 每个病毒有个变异极限 $b_i$，当这个病毒变异到 $b_i$ 时，这个病毒就会停止变异。也就是说，第 $i$ 个病毒最后都会分裂成一个危害值为 $\\{1,2,3,\\ldots,b_i\\}$ 的病毒序列，当所有病","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10407"},"statements":[{"statement_type":"Markdown","content":"在这个游戏里，一开始有 $n$ 个病毒，每个病毒的危害值为 $1$。\n\n每隔一段时间，病毒就会变异，会分裂成两个病毒，右边的病毒会比左边的病毒危害值多 $1$，变异过的病毒不会再变异。\n\n每个病毒有个变异极限 $b_i$，当这个病毒变异到 $b_i$ 时，这个病毒就会停止变异。也就是说，第 $i$ 个病毒最后都会分裂成一个危害值为 $\\{1,2,3,\\ldots,b_i\\}$ 的病毒序列，当所有病毒变异完时，游戏开始，最终变异完的序列是 $\\{1,2,3,\\ldots,b_1,1,2,3,\\ldots,b_2,\\ldots,1,2,3,\\ldots,b_n\\}$。\n\n每次游戏，系统会选择一个区间，myz 需要把这个区间的病毒全部杀死，如果这个区间内的病毒的危害值的最大值是 $x$，那么 myz 需要花费 $x$ 的能量才能消灭它们。\n\n因为不知道系统会选择哪个区间，myz 想知道每个区间需要消耗的**能量值之和**。\n\n由于答案太大了，myz 想让你把答案对 $998244353$ 取模。\n\n## Input\n\n第一行有一个整数 $n$，表示最开始有 $n$ 个病毒。\n\n第二行有 $n$ 个整数，第 $i$ 个整数是 $b_i$，表示第 $i$ 个病毒的变异上限。\n\n## Output\n\n一个整数，表示 myz 需要消耗的能量值之和，答案对 $998244353$ 取模。\n\n[samples]\n\n## Background\n\nmyz 很喜欢玩一款病毒游戏。\n\n## Note\n\n### 样例解释\n第一个样例，病毒最后分裂成 $\\{1,2,1,2,3\\}$，区间  $[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[2,3],[2,4],[2,5],[3,3],[3,4],[3,5],[4,4],[4,5],[5,5]$ 的最小代价和就是 $1+2+2+2+3+2+2+2+3+1+2+3+2+3+3=33$。\n\n### 数据范围\n**本题采用捆绑测试**。\n\nsubtask 编号|$n\\leq$|$b_i\\leq$|特殊性质|分值\n-|-|-|-|-\n$1$|$10^2$|$10^2$|无|$20$\n$2$|$10^4$|$10^2$|无|$20$\n$3$|$10^6$|$10^9$|A|$20$\n$4$|$10^6$|$10^9$|无|$40$\n\n**特殊性质 A**： $b_1 \\leq b_2 \\leq \\ldots \\leq b_n$。\n\n对于 $100\\%$ 的数据，保证 $1\\le n\\le10^6$，$1\\le b_i\\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10407","tags":["动态规划 DP","单调队列"],"sample_group":[["2\n2 3","33"]],"created_at":"2026-03-03 11:09:25"}}