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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <climits>
#include <stack>
#include <time.h>
#define FOR(i,p,k) for(int i = (p);i<(k);i++)
typedef long long int LL;
using namespace std;

int n;
int liczby[200007];
int lenn[200006];
LL poww[20];

LL ans = 0;

// partial specialization optimization for 32-bit numbers
int numDigits(int x)
{
    int ile = 1;
    int mniejszy = 10;
    while(x >= mniejszy) {
        mniejszy*= 10;
        ile++;
    }
    return ile;
}

bool lexi(string a, string b) {
	return a.compare(b) < 0;
}


bool shorter_lexi_equal(int kto, int tacy_sami) {
    int digA = lenn[kto];
    int digB = lenn[kto-1];

    string strA = to_string(liczby[kto]);
    string strB = to_string(liczby[kto-tacy_sami]);

    if(digA <= digB) {
        FOR(i,0,digA) {
            if(strA[i] != strB[i]) {
                return false;
            } 
        }
        return true;
    } else {
        return false;
    }
}

bool czy_moge_uzyc(int kto, int ile_miejsca, int ilosc_powtorek) {
    int koncowka = liczby[kto] % ((int)pow(10, ile_miejsca));
    //cout<<"LICZNE : " <<koncowka<<" "<<ile_miejsca<<" " <<ilosc_powtorek<<endl;

    return pow(10, ile_miejsca) - koncowka >= ilosc_powtorek;

}

int przypadek_dluzy_lexi(int kto, int tacy_sami, int ile_cyfr) {
    int ile1 = lenn[kto-tacy_sami];
    int ile2 = lenn[kto];

    string str1 = to_string(liczby[kto-tacy_sami]);
    string str2 = to_string(liczby[kto]);

    if(ile_cyfr < ile2) {
        return 1;
    }
    
    FOR(i,0,max(ile1,ile2)) {
        int val1 = 0;
        int val2 = 0;

        if(i < ile1) {
            val1 = str1[i];
        }

        if(i < ile2) {
            val2 = str2[i];
        }

        if(val1 > val2) {
            return -1;
        }
        if(val1 < val2) {
            return 1;
        }
    }

    return 0;
}


void licz() {
    int ilosc_cyfr = lenn[0];
    int tacy_sami = 1;
    FOR(i,1,n) {
        int dlugosc = lenn[i];
        int wyn = przypadek_dluzy_lexi(i, tacy_sami,ilosc_cyfr);
        //cout<<"I : "<<i<< " -> "<<wyn<<endl;

        if(wyn == -1 && shorter_lexi_equal(i, tacy_sami)) {
            //jestem leksykograficznie przed , ale jestem rowny na swojej calosci
            int do_zmiany = ilosc_cyfr-lenn[i];
            if(!czy_moge_uzyc(i-tacy_sami, do_zmiany, tacy_sami+1)) {
                ilosc_cyfr++;
                tacy_sami = 1;
            } else {
                tacy_sami++;
            }
        } else if(wyn == 1) {
            //jestem leksykograficznie starszy, w/e
            tacy_sami = 1;
        } else if(wyn == -1) {
            //jestem leksy mniejszy, oraz conajmniej tak samo dlugi
            if(lenn[i] <= ilosc_cyfr) { 
                //cout<<"CO ? : "<<numDigits(liczby[i]) - numDigits(liczby[i-tacy_sami])<<" " <<endl;
                ilosc_cyfr++;
            }
            tacy_sami = 1;
        } else if(wyn == 0 && dlugosc <= ilosc_cyfr) {
            //jestesmy leksykograficznie tacy sami
            //ale jestem nie dluzszy
            //sprawdzam ile da sie jeszcze upchnac
            int do_zmiany = min(ilosc_cyfr-lenn[i-tacy_sami], ilosc_cyfr-dlugosc);
            if(!czy_moge_uzyc(i, do_zmiany, tacy_sami+1)) {
                ilosc_cyfr++;
                tacy_sami = 1;
            } else {
                tacy_sami++;
            }
        } else {
            tacy_sami = 1;
        }

        ans += max(0, ilosc_cyfr-dlugosc);
        ilosc_cyfr = max(ilosc_cyfr, dlugosc);

        // cout<<liczby[i];
        // FOR(i,0,ilosc_cyfr-dlugosc) {
        //     cout<<"0";
        // }
        // cout<<endl;    
    }

}

void dane() {
    poww[0]=1;
    FOR(i,1,8) {
        poww[i] = poww[i-1] * 10;
    }
	cin>>n;
	FOR(i,0,n) {
		cin>>liczby[i];
        lenn[i] = numDigits(liczby[i]);
	}

    licz();
	
	cout<<ans<<endl;

}

int main() {
   
    ios_base::sync_with_stdio(false);
    dane();
    
    return 0;
}