Background

myz really enjoys playing a virus game.

Problem Description

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$.

Input Format

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 Format

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

2
2 3

33

Hint

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.

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