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
98
99
#include <iostream>
//#include <algorithm>
//#include <cmath>
//#include <vector>
//#include <cstdlib>
//#include <stdint.h>
#include <stdio.h>

#ifdef _WIN32
inline int getchar_unlocked() {
    return getchar();
}
#endif

using namespace std;

//typedef int64_t ul;
typedef int ul;

char ch;
//int sign;
inline void readU( ul& x ) {
    x = 0;
    //while((ch < '0' || ch > '9') && ch != '-' && ch != EOF)
    while((ch < '0' || ch > '9') && ch != EOF)
        ch = getchar_unlocked();
    //if (ch == '-')
    //    sign = -1, ch = getchar_unlocked();
    //else
    //    sign = 1;
    do
        x = (x << 3) + (x << 1) + ch - '0';
    while((ch = getchar_unlocked()) >= '0' && ch <= '9');
    //x *= sign;
}

struct Number {
    uint64_t a;
    uint64_t zeros;
    Number(int a) : a(a), zeros(0) {}

    static pair<Number, uint64_t> next(Number T, int n_a) {
        Number res(n_a);
        if (T.zeros == 0 && T.a < res.a) {
            return {res, 0};
        }

        if (T.a < res.a) {
            cout << "normalization fail?" << endl;
            exit(-1);
        }

        // zeros will be needed
        // new number can have len+1 and only zeros
        // or same len, then it will be old+1

        // check if old+1 prefix agree:
        uint64_t t = T.a + 1;
        uint64_t mul = 1;
        uint64_t digs_added = 0;
        while (t > res.a) {
            mul *= 10;
            digs_added++;
            t /= 10;
        }

        if (t == res.a) {
            res.a = T.a + 1;
        } else {
            res.a *= mul;
        }

        res.zeros = T.zeros;
        digs_added += T.zeros;

        while (res.a > 3372036854775807LL) {  // or something...
            res.a /= 10;
            res.zeros++;
        }

        return {res, digs_added};
    }
};

int main() {
    std::ios_base::sync_with_stdio(0);

    int n, ai;
    readU(n);
    Number nb(0);
    uint64_t res = 0;
    while (n--) {
        readU(ai);
        pair<Number, uint64_t> r = Number::next(nb, ai);
        nb = r.first;
        res += r.second;
    }
    cout << res << endl;
}