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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>
#include <sstream>
#include <vector>
#include <map>

using namespace std;



struct number {
    map<int, short int> str;
    int len = 0;
};

//a > b => cmp(a,b) == 1
int cmp(number &a, number &b) {
    if (a.len != b.len)
        return a.len > b.len ? 1 : -1;

    auto x = a.str.begin();
    auto y = b.str.begin();
    while (x != a.str.end() && y != b.str.end()) {
        if (x->first == y->first) {
            if (x->second == y->second) {
                x++;
                y++;
                continue;
            }
            return x->second > y->second ? 1 : -1;
        }
        if (x->first < y->first) {
            if (x->second == 0) {
                x++;
                continue;
            }
            return 1;//x > y
        } else {
            if (y->second == 0) {
                y++;
                continue;
            }
            return -1;//y > x
        }
    }
    while(x != a.str.end()) {
        if(x->second == 0) {
            x++;
            continue;
        }
        return 1;
    }

    while(y != b.str.end()) {
        if(y->second == 0) {
            y++;
            continue;
        }
        return -1;
    }
    return 0;
}


void increase(number &a) {
    int last = a.len - 1;
    while(last > 0 and a.str[last]++ == 9)
        a.str[last--] = 0;
    if (last == 0 && a.str[last]++ == 9) {
        a.str[last] = 1;
        a.str[a.len] = 0;
        a.len++;
    }
}

int common_prefix(number &a, number &b) {
    int i = 0;
    while (i < min(a.len, b.len) && a.str[i] == b.str[i])
        i++;
    return i;
}

int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    int k = 0;
    number a,b;

    string temp;
    cin >> temp;
    a.len = temp.size();
    for (int i = 0;i < temp.size();i++)
        a.str[i] = temp[i] - '0';

    n--;
    long long int sum = 0;
    while(n--) {
        //cout << sum << endl;
        swap(a,b);
    //a is new
        cin >> temp;
        a.len = temp.size();
        a.str = map<int,short int>();
        for (int i = 0;i < temp.size();i++)
            a.str[i] = temp[i] - '0';
        //cout<<n<<endl;
        //cout << a << endl;
        if (cmp(a,b) == 1)
            continue;

        //cout << ":(" << endl;
        int old_len_b = b.len;
        increase(b);
        //cout << b << " "<<a<<endl;
        if (common_prefix(b, a) >= a.len) {
            sum += b.len - a.len;
            swap(a,b);
            continue;
        }
        sum += old_len_b - a.len;
        a.len = old_len_b;
        if (cmp(a,b) >= 0)
            continue;
        sum++;
        a.len++;
    }
    cout << sum << endl;
    return 0;
}