P16267 [Lanqiao Cup 2026 NOI Qualifier Python B Group] Digit Count Sum

Xiao Lan has recently been studying interval statistics problems. Given a sequence $a_1, a_2, \dots, a_n$ of length $n$, in the original problem, you need to compute $$ \sum_{l=1}^{n} \sum_{r=l}^{n} (r - l + 1) \max_{l \leq i \leq r} a_i $$ That is, for every interval $[l, r]$ in the sequence, take the interval length $(r - l + 1)$ and the interval maximum $\max_{l \leq i \leq r} a_i$, multiply them, and sum the results over all intervals. However, Xiao Lan feels that directly using the interval length is a bit monotonous, so he makes a small modification to this problem. He defines a function $f(x)$ to be the number of digits of the integer $x$ in its decimal representation. For example: $f(998244353) = 9$, $f(799) = 3$. Now, for each interval $[l, r]$, Xiao Lan no longer uses the interval length itself, but uses the number of digits of the interval length, $f(r - l + 1)$. Therefore, he wants you to compute the value of the following expression: $$ \sum_{l=1}^{n} \sum_{r=l}^{n} f(r - l + 1) \max_{l \leq i \leq r} a_i $$ Since the answer may be very large, you only need to output the result modulo $998244353$.

The input consists of two lines. The first line contains a positive integer $n$, representing the length of the sequence. The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$, representing the given sequence.

Output one line containing an integer, representing $\sum_{l=1}^{n} \sum_{r=l}^{n} f(r - l + 1) \max_{l \leq i \leq r} a_i$ modulo $998244353$.

### Constraints For $30\%$ of the testdata, $n \leq 500$. For $60\%$ of the testdata, $n \leq 3000$. For all testdata, $1 \leq n \leq 500000$, $1 \leq a_i \leq 10^9$. Translated by ChatGPT 5