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

using namespace std;

vector<char> split(long long t) {
    vector<char> res;
    while(t) {
        res.push_back(t % 10);
        t /= 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

class Num {
public:
    vector<char> w;
    int extra = 0;
    const int LIMIT = 22;

    Num() {
        w.push_back(0);
        extra = 0;
    }

    int length() {
        return extra + (int)w.size();
    }

    void print_w() {
        for (int d : w) {
            printf("%d", d);
        }
        if (extra) {
            printf(" extra = %d", extra);
        }
        printf("\n");
    }

    void increment() {
        for(int i = w.size() - 1; i >= 0; i--) {
            if (w[i] < 9) {
                w[i]++;
                return;
            } else {
                w[i] = 0;
            }
        }
        w.insert(w.begin(), 1);
    }

    void build_w_from_vx(const vector<char> & vx, int add_zeroes) {
        w = vx;
        while(add_zeroes && w.size() < LIMIT) {
            add_zeroes--;
            w.push_back(0);
        }
        extra = add_zeroes;
    }

    void update_w(const vector<char> & vx) {
        if (vx.size() > length()) {
            build_w_from_vx(vx, 0);
            return;
        }
        for (int i = 0; i < vx.size(); i++) {
            if (w[i] < vx[i]) {
                build_w_from_vx(vx, length() - vx.size());
                return;
            }
            if (w[i] > vx[i]) {
                build_w_from_vx(vx, length() - vx.size() + 1);
                return;
            }
        }
        // vx is prefix of w, so do nothing
    }

    int update(int x) {
        vector<char> vx = split(x);
        update_w(vx);
        return (int)vx.size();
    }
};

int main() {
    int n;
    scanf("%d", &n);
    Num num;
    long long ans = 0;
    bool DEBUG = false;
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);

        num.increment();

        if (DEBUG) {
            printf("x = %d\n", x);
            printf("w = ");
            num.print_w();
        }
        int xlen = num.update(x);

        if (DEBUG) {
            printf("v = ");
            num.print_w();
            printf("adding %d\n\n", num.length() - xlen);
        }

        ans += num.length() - xlen;
    }
    printf("%lld\n", ans);
    return 0;
}