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


using namespace std;

struct Array {
    int timer = 0;

    vector <int> tab, lastUsed;

    Array() {}
    Array(const vector <int> &v): tab(v), lastUsed(v.size(), 0) {}

    inline void access(int i) {
        if (lastUsed[i] < timer) { tab[i] = 0; lastUsed[i] = timer; }
    }

    int& operator[](int i) {
        access(i);
        return tab[i];
    }

    void clearAll() { timer++; }

    int size() { return tab.size(); }

    void extend() { tab.push_back(0); lastUsed.push_back(timer); }

    vector <int> getPrefix(int len) {
        assert(len <= size());

        vector <int> result(len);
        for (int i = 0; i < len; i++) {
            result[i] = (*this)[i];
        }

        return result;
    }

    void setPrefix(const vector <int> &v) {
        assert((int) v.size() <= size());
        for (int i = 0; i < (int) v.size(); i++) {
            (*this)[i] = v[i];
        }
    }
};

vector <int> readDigits() {
    string s;
    cin >> s;

    vector <int> digits(s.size());
    for (int i = 0; i < (int) s.size(); i++) {
        digits[i] = s[i] - '0';
    }

    return digits;
}

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

    int n;
    cin >> n;

    long long ans = 0;
    Array curr;
    
    while (n--) {
        auto x = readDigits();
        int xSize = x.size();

        if (xSize > curr.size()) {
            curr = Array(x);
        } else if (xSize == curr.size()) {
            int i = 0;
            while (i < xSize && x[i] == curr[i]) {
                i++;
            }
        
            if (i < xSize && x[i] > curr[i]) {
                curr = Array(x);
            } else {
                curr = Array(x);
                curr.extend();
            }
        } else {
            auto pref = curr.getPrefix(xSize);
            if (x > pref) {
                curr.clearAll();
                curr.setPrefix(x);
            } else if (x < pref) {
                curr.clearAll();
                curr.setPrefix(x);
                curr.extend();
            } else {
                int firstNotNine = -1;
                for (int i = curr.size() - 1; i >= xSize; i--) {
                    if (curr[i] != 9) {
                        firstNotNine = i;
                        break;
                    }
                }

                if (firstNotNine == -1) {
                    curr.clearAll();
                    curr.setPrefix(x);
                    curr.extend();
                } else {
                    curr.setPrefix(x);
                    curr[firstNotNine]++;

                    for (int i = firstNotNine + 1; i < curr.size(); i++) {
                        curr[i] = 0;
                    }
                }
            }
        }

        ans += curr.size() - xSize;
    }

    cout << ans;

    return 0;
}