蓝桥杯2026年第十七届省赛真题-位数求和

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

给定一个长度为 n 的序列 a1, a2,. . . , an，如果按照最初的问题，需要计算的是

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

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

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

f(998244353) = 9 ,

f(799) = 3 。

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

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

输入共两行。

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

第二行包含 n 个正整数 a1, a2,. . . , an，表示给定的序列。

输出一行，包含一个整数，表示 ∑ⁿ_l=1 ∑ⁿ_r=l f(r−l+1) max_l≤i≤r a_i 对 998244353取模后的结果。

【样例输入 2】

10

12 3 4 5 6 7 8 9 10

【样例输出 2】

395

【评测用例规模与约定】

对于 30% 的评测用例，n ≤ 500；

对于 60% 的评测用例，n ≤ 3000；

对于所有的评测用例，1 ≤ n ≤ 500000，1 ≤ a_i ≤ 10⁹。