P9461 "EZEC-14" Mode II

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

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

The first line contains an integer $n$. The second line contains $n$ integers $a_i$.

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

**[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