Problem Description

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

Input Format

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 Format

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

5
1 2 3 4 5

55

10
1 2 3 4 5 6 7 8 9 10

395

Hint

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