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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include <iostream>

#define ll long long

using namespace std;

ll tab[200005];
ll len[200005];
ll add[200005];
ll val[200005];
ll fir[200005];

ll length (ll x)
{
    ll ans=0;
    while (x!=0)
    {
        x/=10; ans++;
    }
    return ans;
}
bool ten (ll x)
{
    while (x>=10)
    {
        if ((x%10)!=0) return false;
    }
    if (x!=1) return false;
    return true;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n; cin>>n;
    ll ans=0;
    for (ll i=1; i<=n; i++)
    {
        cin>>tab[i];
        len[i]=length(tab[i]);
    }
    for (ll i=2; i<=n; i++)
    {
        ll dif;
        ll num_1=tab[i-1];
        ll num_2=tab[i];
        if (len[i]>(len[i-1]+add[i-1])) continue;
        if (len[i]==(len[i-1]+add[i-1]))
        {
            dif=len[i]-len[i-1];
            for (ll j=0; j<dif; j++) num_1*=10;
            num_1+=val[i-1];
            if (num_1<num_2) continue;
            ans++; add[i]++;
            continue;
        }
        if (len[i-1]==len[i])
        {
            if (tab[i-1]<tab[i])
            {
                add[i]=add[i-1];
            }
            else if (tab[i-1]>tab[i])
            {
                add[i]=add[i-1]+1;
            }
            else if (tab[i-1]==tab[i])
            {
                if (add[i-1]>=17)
                {
                    add[i]=add[i-1];
                    tab[i]=tab[i-1];
                    val[i]=val[i-1];
                    len[i]=len[i-1];
                }
                else
                {
                    ll pom=1;
                    for (ll j=0; j<add[i-1]; j++) pom*=10;
                    pom--;
                    if (val[i-1]==pom)
                    {
                        add[i]=add[i-1]+1;
                    }
                    else
                    {
                        add[i]=add[i-1];
                        val[i]=val[i-1]+1;
                    }
                }
            }
        }
        else if (len[i-1]>len[i])
        {
            dif=len[i-1]-len[i];
            ll qqq=len[i-1]+add[i-1]-len[i];
            for (ll j=0; j<dif; j++) num_1/=10;
            if (num_1<tab[i])
            {
                add[i]=qqq;
            }
            else if (num_1>tab[i])
            {
                add[i]=qqq+1;
            }
            else if (num_1==tab[i])
            {
                if (add[i-1]>=17)
                {
                    add[i]=add[i-1];
                    tab[i]=tab[i-1];
                    val[i]=val[i-1];
                    len[i]=len[i-1];
                }
                else
                {
                    ll jan=1, roman=1;
                    for (ll j=0; j<dif; j++) jan*=10;
                    jan--;
                    for (ll j=0; j<add[i-1]; j++) roman*=10;
                    roman--;
                    ll pom=1;
                    for (ll j=0; j<dif; j++) pom*=10;
                    if (((tab[i-1]%pom)==jan) && (val[i-1]==roman))
                    {
                        add[i]=qqq+1;
                    }
                    else if (val[i-1]==roman)
                    {
                        tab[i]=tab[i-1]+1;
                        len[i]=len[i-1];
                        add[i]=add[i-1];
                        ans+=dif;
                    }
                    else
                    {
                        tab[i]=tab[i-1];
                        len[i]=len[i-1];
                        add[i]=add[i-1];
                        val[i]=val[i-1]+1;
                        ans+=dif;
                    }
                }
            }
        }
        else if (len[i-1]<len[i])
        {
            dif=len[i]-len[i-1];
            for (ll j=0; j<dif; j++) num_1*=10;
            ll qqq=len[i-1]+add[i-1]-len[i];
            ll pom=val[i-1];
            if (add[i-1]<17)
            {
                for (ll j=0; j<qqq; j++) pom/=10;
                num_1+=pom;
            }
            if (num_1<tab[i])
            {
                add[i]=qqq;
            }
            if (num_1>tab[i])
            {
                add[i]=qqq+1;
            }
            if (num_1==tab[i])
            {
                if (add[i-1]>=17)
                {
                    add[i]=qqq;
                    val[i]=val[i-1]+1;
                }
                else
                {
                    for (ll j=0; j<qqq; j++) pom*=10;
                    val[i-1]-=pom;
                    ll xxx=1;
                    for (ll j=0; j<qqq; j++) xxx*=10;
                    xxx--;
                    if (val[i-1]==xxx)
                    {
                        add[i]=qqq+1;
                    }
                    else
                    {
                        add[i]=qqq;
                        val[i]=val[i-1]+1;
                    }
                }
            }
        }
        ans+=add[i];
    }
    cout<<ans<<"\n";
}