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
#include <iostream>
#define LL long long
#define MAX_LENGTH 200100

using namespace std;

int main()
{
    LL N, a, count = 0, num_len = 0, value_len, num_pos;
    LL i, j, inc, last_incomplete_pos = 0, local_last_incomplete_pos = 0;
    LL empty_start = -1, empty_stop = -1;
    int num[MAX_LENGTH], value[20], pv, v;
    short comp_status;

    cin >> N;
    for (i = 0; i < N; ++i) {
        cin >> a;
        value_len = 0;
        while (a > 0) {
            value[value_len++] = a % 10;
            a /= 10;
        }
        if (value_len > num_len) {
            num_len = 0;
            while (value_len-- > 0) {
                v = value[value_len];
                if (v < 9)
                    last_incomplete_pos = num_len;
                num[num_len++] = v;
            }
            inc = 0;
        } else {
            num_pos = 0;
            comp_status = 0;
            local_last_incomplete_pos = 0;
            while (value_len-- > 0) {
                if (num_pos >= empty_start && num_pos <= empty_stop) {
                    pv = 0;
                } else {
                    pv = num[num_pos];
                }
                v = value[value_len];
                if (comp_status == 0 && pv != v) {
                    if (pv > v) {
                        comp_status = -1;
                    } else {
                        comp_status = 1;
                    }
                }
                if (v < 9)
                    local_last_incomplete_pos = num_pos;
                num[num_pos++] = v;
            }

            if (comp_status == 0 && last_incomplete_pos < num_pos) {
                comp_status = -1;
            }

            if (comp_status == 0) {
                if (empty_stop > -1) {
                    if (num_pos > empty_stop) {
                        empty_start = -1;
                        empty_stop = -1;
                    } else if (num_pos > empty_start) {
                        empty_start = num_pos;
                    }
                }

                ++num[last_incomplete_pos];
                if (last_incomplete_pos == num_len - 1) {
                    if (num[last_incomplete_pos] == 9) {
                        while (last_incomplete_pos-- > 0){
                            if (last_incomplete_pos >= empty_start && last_incomplete_pos <= empty_stop) {
                                num[last_incomplete_pos] = 0;
                                if (--empty_stop < empty_start) {
                                    empty_start = -1;
                                    empty_stop = -1;
                                }
                                break;
                            } else if (num[last_incomplete_pos] < 9)
                                break;
                        }
                    }
                } else {
                    for (j = last_incomplete_pos + 1; j < num_len; j++)
                        num[j] = 0;
                    last_incomplete_pos = num_len - 1;
                }
            } else {
                if (comp_status == -1)
                    num_len++;
                if (num_pos < num_len) {
                    last_incomplete_pos = num_len - 1;
                    num[last_incomplete_pos] = 0;
                    if (num_pos + 1 < num_len) {
                        empty_start = num_pos;
                        empty_stop = last_incomplete_pos - 1;
                    } else {
                        empty_start = -1;
                        empty_stop = -1;
                    }
                } else {
                    last_incomplete_pos = local_last_incomplete_pos;
                    empty_start = -1;
                    empty_stop = -1;
                }
            }
            inc = num_len - num_pos;
        }
        count += inc;
    }
    cout << count << endl;
    return 0;
}