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
100
101
102
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <cstdint>

using namespace std;
static int N;

int64_t compare_prefix(string& a, string& b) {
    auto len = min(a.length(), b.length());
    for (int i = 0; i < len; ++i) {
        int res = a[i] - b[i];
        if (res != 0) {
            return res;
        }
    }
    return 0;
}

int64_t compare(string& a, string& b) {
    auto ld = a.length() - b.length();
    if (ld != 0)
        return ld;
    else
        return compare_prefix(a, b);
}

bool nines_remaining(string& a, string& b) {
    assert(a.length() < b.length());
    auto len = min(a.length(), b.length());
    for (int i = len; i < b.length(); ++i) {
        if (b[i] != '9') return false;
    }
    return true;
}

int last_non_nine(string& a) {
    for (int i = a.length() - 1; i >= 0; --i) {
        if (a[i] != '9') {
            return i;
        }
    }
    return -1;
}

int main() {
    cin >> N;
    vector<string> a;
    string w;
    for (int i = 0; i < N; ++i) {
        cin >> w;
        a.push_back(w);
    }
    uint64_t res = 0;
    for (int i = 1; i < N; ++i) {
        int num = 0;
        string& prev = a[i - 1];
        string& curr = a[i];

        auto pl = prev.length();
        auto cl = curr.length();
        // cout << i << " " << pl << " " << cl << endl;
        if (pl < cl) {
            continue;
        } else if (pl == cl) {
            auto diff = compare(prev, curr);
            if (diff >= 0) {
                num++;
                curr.push_back('0');
            }
        } else {
            auto res = compare_prefix(prev, curr);
            if (res < 0) {
                // pad with zeros
                while (prev.length() > curr.length()) {
                    curr.push_back('0');
                    num++;
                }
            } else if (res == 0 && !nines_remaining(curr, prev)) {
                int last = last_non_nine(prev);
                assert(last != -1);
                while (prev.length() > curr.length()) {
                    num++;
                    auto len = curr.length();
                    curr.push_back(prev[len]);
                    if (len == last) {
                        curr.back()++;
                    }
                }
            } else {
                while (prev.length() >= curr.length()) {
                    curr.push_back('0');
                    num++;
                }
            }
        }
        res += num;
    }
    cout << res << endl;
    return 0;
}