1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
const int N = 2e5 + 5, D = 10;
int n, a, dl[N], roz[N], cyf[N][D+1], pot[D];
stack<int> S1;
int main()
{
        pot[0]=1;
        for(int i=1;i<D;i++) pot[i] = 10 * pot[i-1];
        scanf("%d", &n);
        for(int i=1;i<=n;i++)
        {
                scanf("%d", &a);
                int k = a;
                while(k)
                {
                        dl[i]++;
                        S1.push(k%10);
                        k/=10;
                }
                dl[i]--;
                int it = 0;
                while(!S1.empty())
                {
                        cyf[i][it] = S1.top();
                        it++;
                        S1.pop();
                }
        }
        int len = 0;
        int num = 0;
        int sublen = 0;
        long long ans = 0;
        for(int i=1;i<=n;i++)
        if(len < dl[i]) len = dl[i];
        else
        {
                int it = 0;
                while(it <= dl[i] && cyf[i][it]==cyf[i-1][it]) it++;
                if(it <= dl[i])
                {
                        if(cyf[i][it] < cyf[i-1][it]) len++;
                        num = 0;
                        sublen = max(0, len - 9);
                }
                else
    {
                        for(int j=dl[i]+1;j<D;j++) cyf[i][j] = cyf[i-1][j];
                        num++;
                        if(sublen < D)
                        if(num == pot[sublen])
                        {
                                num = 0;
                                bool zn = 0;
                                for(int j = min(len, 9);j>dl[i];j--)
                                if(cyf[i][j]==9) cyf[i][j]=0;
                                else
                                {
                                        zn = 1;
                                        cyf[i][j]++;
                                        break;
                                }
                                if(!zn) len++;
                        }
                        sublen = max(0, len - 9);
                }
                ans += len - dl[i];
        }
        printf("%lld", ans);
        return 0;
}