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
#include <bits/stdc++.h>
using namespace std;

template <typename T> T load() { T r; cin >> r; return r; }
template <typename T> vector<T> loadMany(long long n) { vector<T> rs(n); generate(rs.begin(), rs.end(), &load<T>); return rs; }

long long len10(long long x) {
    auto r = 0;
    while (x != 0)
        ++r, x /= 10;
    return r;
}

template <typename T> vector<T> preprocessExp(const T& a, long long n) {
    auto tab = vector<T>(n+1);
    tab[0] = 1;
    for (auto i=0; i<n; ++i)
        tab[i+1] = tab[i] * a;
    return tab;
}

struct Funny {
    long long fix;
    long long count;
    long long pad;
    bool separated() const {
        return pad + len10(fix) > 10 + 6;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    auto n = load<long long>();
    auto xs = loadMany<long long>(n);
    auto exp10 = preprocessExp<long long>(10, 18);
    auto total = 0ll;
    auto left = Funny{0, 0, 0};
    for (auto x : xs) {
        auto l1 = len10(left.fix);
        auto l2 = len10(x);
        auto z1 = left.pad;
        if (l1 + z1 < l2) {
            left = Funny{x, 0, 0};
        } else {
            auto z2 = l1 + z1 - l2;
            if (left.separated()) {
                auto pre1 = left.fix * exp10[max(l2 - l1, 0ll)] / exp10[max(l1 - l2, 0ll)];
                auto pre2 = x;
                auto extended = left.fix * exp10[max(l2 - l1, 0ll)];
                if (pre1 < pre2) {
                    left = Funny{x, 0, z2};
                } else if (pre1 == pre2) {
                    auto newpad = l1 + z1 - max(l1, l2);
                    auto realpad = z2;
                    left = Funny{extended, left.count + 1, newpad};
                    total -= newpad;
                    total += realpad;
                } else {
                    left = Funny{x, 0, z2+1};
                }
            } else {
                auto whole1 = left.fix * exp10[z1] + left.count;
                auto pre1 = whole1 / exp10[z2];
                auto pre2 = x;
                auto suf1 = whole1 % exp10[z2];
                if (pre1 < pre2) {
                    left = Funny{x, 0, z2};
                } else if (pre1 == pre2 and suf1 != exp10[z2]-1) {
                    left = Funny{x, suf1 + 1, z2};
                } else if (pre1 == pre2 and suf1 == exp10[z2]) {
                    left = Funny{x, 0, z2+1};
                } else {
                    left = Funny{x, 0, z2+1};
                }
            }
        }
        total += left.pad;
    }
    cout << total << '\n';
}