题意简述

给定一个长度为 ( N ) 的正整数序列 ( a )，每次操作可以在某个数的末尾（十进制最后）添加一个数字（0~9）。目标是通过若干次操作使序列严格单调递增，求最小操作次数。

核心思路

从左到右依次处理相邻两个数，保证每个数在满足大于前一个数的情况下，添加的位数最少。

设前一个数最终变为 $\text{prev}$，当前数为 ( b )，长度分别为 ( L_p )、( L_b )。

比较逻辑：

1. 如果 $b > \text{prev}$，则不需要修改 ( b )。
2. 否则，尝试在 ( b ) 后面添加若干数字，使新数 $b' > \text{prev}$：
   • 取 $\text{prev}$ 的前 $L_b$ 位，记为$\text{pref}$。
   • 若 $b > \text{pref}$：则只需补到长度 ( L_p )，添加 ( L_p - L_b ) 个 0 即可。
   • 若 $b < \text{pref}$：必须补到长度 ( L_p + 1 )，添加 ( L_p + 1 - L_b ) 个 0。
   • 若$b = \text{pref}$：
     • 若 $\text{prev}$ 去掉前缀后不是全 9，则补到长度 ( L_p ) 且后缀 = 原后缀 + 1。
     • 若是全 9，则必须补到长度 $L_p + 1$（加一个 0 即可）。

更新 $\text{prev}$ 为新的 $b'$，累加添加的位数到答案。

时间复杂度

$O(N \cdot \text{位数})$，可轻松通过$N \le 2\times 10^5$ 的数据范围。

示例

输入：

3
8
5
13

过程：

• prev=8, b=5, 5<8, 需补到长度 2 ⇒ 50，操作+1。
• prev=50, b=13, 13<50，需补到长度 3 ⇒ 130，操作+1。 总操作次数 = 2，输出 2。