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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

const int N = 200000, MAX = 18;
int p[N], q[N];
long long x[N];
string s[N];

string itos( long long a )
{
    string result;

    while ( a )
    {
        result.push_back( a%10 + '0' );
        a /= 10;
    }
    reverse( result.begin(), result.end() );
    return result;
}

bool cmp( string a, string b, bool flag = true )
{
    if ( a.size() <= b.size() ) return false;

    for ( int i = 0; i < b.size(); ++i )
    {
        if ( a[i] != b[i] ) return false;
    }
    if ( flag )
    {
        for ( int i = b.size(); i < a.size(); ++i )
        {
            if ( a[i] != '9' ) return true;
        }
        return false;
    }
    else return true;
}

int main()
{
    int n, t;
    long long answer = 0;

    scanf( "%d", &n );
    for ( int i = 0; i < n; ++i )
    {
        scanf( "%d", &p[i] );
        x[i] = p[i];
        s[i] = itos( p[i] );
        q[i] = s[i].size();
    }

    for ( t = 1; t < n; ++t )
    {
        if ( s[t-1].size() >= MAX ) break;

        if ( cmp( s[t-1], s[t] ) )
        {
            answer += s[t-1].size() - s[t].size();
            x[t] = x[t-1]+1;
            s[t] = itos( x[t] );
        }
        else
        {
            while ( x[t] <= x[t-1] )
            {
                answer++;
                x[t] *= 10;
                s[t].push_back( '0' );
            }
        }
    }

    s[t-1] = itos( p[t-1] );
    q[t-1] = MAX;

    for ( t; t < n; ++t )
    {
        if ( !cmp( s[t-1], s[t] ) && s[t] < s[t-1] )
        {
            answer += q[t-1] - q[t] + 1;
            q[t] = q[t-1] + 1;
        }
        else
        {
            answer += q[t-1] - q[t];
            q[t] = q[t-1];
        }
    }

    printf ( "%lld\n", answer );
}