Background

dXqwq is an unlovely boy. In the mode problem of NOI2022, he defined $10^6$ std::deque and successfully got MLE.

Problem Description

Given a sequence $a$ of length $n$, we construct a sequence $b$ in the following way:

• Initially, $b$ is an empty sequence.
• For $i=1,2,\cdots,n$, we append $1,2,\cdots,a_i$ to the end of $b$ in order.

dXqwq defines the minimum mode of a sequence as the smallest value among all numbers with the maximum frequency. For example, the minimum mode of $[1,1,4,5,1,4]$ is $1$, and the minimum mode of $[1,14,5,14,19,19,8,10]$ is $14$.

You need to compute the sum of the minimum mode over every subarray of $b$. Since the answer may be very large, output it modulo $998244353$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $a_i$.

Output Format

Output one integer, representing the sum of the minimum mode over every subarray of $b$ modulo $998244353$.

3
1 2 3

28

9
9 9 8 2 4 4 3 5 3

1912

Hint

[Sample Explanation]

In the first sample, $b=[1,1,2,1,2,3]$.

There are $15$ subarrays whose minimum mode is $1$, $5$ subarrays whose minimum mode is $2$, and $1$ subarray whose minimum mode is $3$. Therefore, the answer is $15\times 1+5\times 2+1\times 3=28$.

[Hint]

Allocating $10^6$ std::deque will definitely cause MLE under a 512MB memory limit.

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (10 pts): $\sum a_i\leq 100$.
• Subtask 2 (20 pts): $\sum a_i\leq 10^3$.
• Subtask 3 (20 pts): $\sum a_i\leq 10^6$.
• Subtask 4 (10 pts): $n\leq 2$.
• Subtask 5 (20 pts): $n\leq 10^3$.
• Subtask 6 (10 pts): $a_i\leq 2$.
• Subtask 7 (10 pts): no special constraints.

For $100\%$ of the testdata, $1\leq n\leq 10^6$, $1\leq a_i\leq 10^6$.

Translated by ChatGPT 5