P10407 「SMOI-R1」Game

myz really enjoys playing a virus game.

In this game, there are initially $n$ viruses, and each virus has a hazard value of $1$. After some time, a virus mutates and splits into two viruses. The virus on the right has a hazard value $1$ higher than the virus on the left. A virus that has mutated will not mutate again. Each virus has a mutation limit $b_i$. When the virus mutates up to $b_i$, it stops mutating. That is, the $i$-th virus will finally split into a virus sequence with hazard values $\{1,2,3,\ldots,b_i\}$. When all viruses have finished mutating, the game starts. The final sequence is $\{1,2,3,\ldots,b_1,1,2,3,\ldots,b_2,\ldots,1,2,3,\ldots,b_n\}$. In each game, the system selects an interval, and myz needs to kill all viruses in this interval. If the maximum hazard value among the viruses in this interval is $x$, then myz needs to spend $x$ energy to eliminate them. Since myz does not know which interval the system will choose, he wants to know the **sum of the energy values** required for every interval. Because the answer is too large, output the answer modulo $998244353$.

The first line contains an integer $n$, indicating that there are initially $n$ viruses. The second line contains $n$ integers. The $i$-th integer is $b_i$, indicating the mutation limit of the $i$-th virus.

Output one integer, representing the total energy myz needs to spend, modulo $998244353$.

### Sample Explanation In the first sample, the viruses finally split into $\{1,2,1,2,3\}$. The sum of the minimum costs for intervals $[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]$ is $1+2+2+2+3+2+2+2+3+1+2+3+2+3+3=33$. ### Constraints **This problem uses bundled testdata**. subtask ID|$n\leq$|$b_i\leq$|Special Property|Score -|-|-|-|- $1$|$10^2$|$10^2$|None|$20$ $2$|$10^4$|$10^2$|None|$20$ $3$|$10^6$|$10^9$|A|$20$ $4$|$10^6$|$10^9$|None|$40$ **Special Property A**: $b_1 \leq b_2 \leq \ldots \leq b_n$. For $100\%$ of the testdata, it is guaranteed that $1\le n\le10^6$ and $1\le b_i\le 10^9$. Translated by ChatGPT 5