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
#include <iostream>
#include <math.h>
#include <climits>
#include <cstdio>


using namespace std;


const bool DEBUG = false; 
const long long mypow10[] = {(long long)1, (long long)1e1, (long long)1e2, (long long)1e3, (long long)1e4, (long long)1e5, (long long)1e6, (long long)1e7, (long long)1e8, (long long)1e9, (long long)1e10, (long long)1e11, (long long)1e12, (long long)1e13, (long long)1e14, (long long)1e15};


struct number{
    long long base;
    int zeroes_added;
    int counter;
    number(long long a, long long z=0, long long c=0): base(a), zeroes_added(z), counter(c){}
};


const long long MAX_BASE = (long long)1e13;

int numDigits(long long number)
{
    int digits = 0;
    if (number < 0) digits = 1; // remove this line if '-' counts as a digit
    while (number) {
        number /= 10;
        digits++;
    }
    return digits;
}


int lexcomp(long long a, long long b){
    int _a = numDigits(a), _b = numDigits(b);
    if(_a <= _b) return a*mypow10[_b - _a] < b;
    return false;
}


bool is_prefix(long long a, long long b){
    if(a > b)
        return false;
    int diff = numDigits(b) - numDigits(a);
    b /= mypow10[diff];
    return a == b;
}


int len(number const & a){
    return numDigits(a.base) + a.zeroes_added;
}

number normalize(long long a, int length){
    // cout << "normalize: " << a << '\n';
    int zeroes = length - numDigits(a);
    if( zeroes <= 0 )
        return number(a, 0, 0);
    int to_add = 13 - numDigits(a);
    int l = (zeroes <= to_add)? zeroes: to_add;
    return number(a*mypow10[l], zeroes - l, 0);
}

number increment(long long prefix, number const & last){
    if( last.zeroes_added > 11 || last.counter != mypow10[last.zeroes_added] - 1 )
        return number(last.base, last.zeroes_added, last.counter+1);
    int diff_digits = numDigits(last.base) - numDigits(prefix);
    long long a = prefix * mypow10[diff_digits];
    long long diff = last.base - a;
    if(prefix == last.base)
        return normalize(a, len(last) + 1);
    
    if(DEBUG){
        printf("diff: %lld | a:%lld\n", diff, a);
        printf("diff_digits: %d\n", diff_digits);
    }
    
    if ( diff + 1 != mypow10[diff_digits] ) // (67999, 1, 9), 67 -> (67000, 2, 0)  
        return number(a + diff + 1, last.zeroes_added, 0);
  
    return normalize(a, len(last) + 1);
}


number new_last(int a, number const & last){
    if( is_prefix(a, last.base) ){
        // printf("is_prefix(%d, %lld)\n",a, last.base);
        return increment(a, last);

    }
    if( lexcomp(a, last.base) ) // if a < last.base (filled with 0s)
        return normalize(a, len(last) + 1);
    return normalize(a, len(last)); // if a > last.base (filled with 0s)
}



int main(){
    std::ios::sync_with_stdio(false);

    long long n, a;
    long long res = 0;
    cin >> n;
    cin >> a;
    number last_number = number(a, 0, 0);
    n--;

    if(DEBUG) printf("%lld\n", a);
    while(n--){
        cin >> a;
        if(DEBUG) printf("processing %lld\n", a);
        number new_number = new_last(a, last_number);
        if(DEBUG) printf("%lld e%d+%d\n", new_number.base, new_number.zeroes_added, new_number.counter);
        res += len(new_number) - numDigits(a);
        last_number = new_number;
        if(DEBUG) printf("\n");
    }

    cout << res << '\n';

    return 0;
}