题目描述

小蓝最近在研究区间统计问题。

给定一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，如果按照最初的问题，需要计算的是

$$\sum_{l=1}^{n} \sum_{r=l}^{n} (r - l + 1) \max_{l \leq i \leq r} a_i$$

也就是说，对于序列中的每一个区间 $[l, r]$，取出这个区间的长度 $(r - l + 1)$ 与区间最大值 $\max_{l \leq i \leq r} a_i$，将二者相乘，并对所有区间的结果求和。

不过，小蓝觉得直接使用区间长度有些单调，于是他对这个问题作了一点修改。

他定义函数 $f(x)$ 表示整数 $x$ 在十进制表示下的位数。例如：

$f(998244353) = 9$，

$f(799) = 3$。

现在，对于每一个区间 $[l, r]$，小蓝不再使用区间长度本身，而是使用区间长度的位数 $f(r - l + 1)$。因此，他希望你计算下面这个式子的值：

$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(r - l + 1) \max_{l \leq i \leq r} a_i$$

由于答案可能非常大，你只需要输出结果对 $998244353$ 取模后的值。

输入格式

输入共两行。

第一行包含一个正整数 $n$，表示序列的长度。

第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示给定的序列。

输出格式

输出一行，包含一个整数，表示 $\sum_{l=1}^{n} \sum_{r=l}^{n} f(r - l + 1) \max_{l \leq i \leq r} a_i$ 对 $998244353$ 取模后的结果。

5
1 2 3 4 5

55

10
1 2 3 4 5 6 7 8 9 10

395

提示

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$n \leq 500$；

对于 $60\%$ 的评测用例，$n \leq 3000$；

对于所有的评测用例，$1 \leq n \leq 500000$，$1 \leq a_i \leq 10^9$。