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

using namespace std;
long long dp[8],n,t[200005],l[21],p[21],a,ile,ok,akt,akt2,dl,liczba,zlicz,poprz_ile,dod;
long long ans;
vector<long long>v;
int main()
{
    scanf("%lld",&n);
    dp[0]=1;
    for(int i=1;i<=7;i++)dp[i]=dp[i-1]*10;
    for(int i=1;i<=20;i++)l[i]=p[i]=-1;
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=20;i++)p[i]=-1;
        scanf("%lld",&t[k]);
        a=t[k];
        ile=0;
        v.clear();
        while(a!=0)
        {
            v.push_back(a%10);
            a/=10;
            ile++;
        }
        akt=v.size()-1;
        akt2=1;
        ok=1;
        while(akt>=0)
        {
            if(l[akt2]<v[akt])
            {
                ok=2;
                break;
            }
            else if(l[akt2]>v[akt])
            {
                ok=0;
                break;
            }
            akt2++;
            akt--;
        }
        akt=0;
        for(int i=v.size()-1;i>=0;i--)
        {
            p[++akt]=v[i];
            //cout<<p[akt];
        }
        if(ile>dl)
        {
            for(int i=1;i<=20;i++)l[i]=p[i];
            dl=ile;
            //cout<<endl;
            //cout<<dl<<endl<<endl;
            continue;
        }
        //cout<<ok<<endl;
        akt=ile;
        if(ok==0)
        {
            dl++;
            ans=ans+dl-ile;
            if(dl>16)
            {
                p[++akt]=-1;
                //cout<<" ";
                for(int i=1;i<=6;i++)
                {
                    p[++akt]=0;
                    //cout<<p[akt];
                }
            }
            else for(int i=ile+1;i<=dl;i++)
            {
                p[++akt]=0;
                //cout<<p[akt];
            }
        }
        else if(ok==2)
        {
            ans=ans+dl-ile;
            if(dl>16)
            {
                p[++akt]=-1;
                //cout<<" ";
                for(int i=1;i<=6;i++)
                {
                    p[++akt]=0;
                    //cout<<p[akt];
                }
            }
            else for(int i=ile+1;i<=dl;i++)
            {
                p[++akt]=0;
                //cout<<p[akt];
            }
        }
        else
        {
            if(dl<=16)akt=ile;
            else
            {
                akt=0;
                while(l[akt+1]!=-1)akt++;
                akt++;
            }
            liczba=0;
            v.clear();
            while(l[++akt]!=-1)
            {
                v.push_back(l[akt]);
                liczba=liczba*10+l[akt];
            }
            akt=ile;
            if(liczba+1==dp[v.size()])
            {
                dl++;
                for(int i=0;i<v.size();i++)v[i]=0;
                v.push_back(0);
            }
            else
            {
                if(dl>16)
                {
                    for(int i=1;i<=20;i++)
                    {
                        if(l[i]==-1)
                        {
                            akt=i-1;
                            break;
                        }
                        p[i]=l[i];
                    }
                }
                for(int i=v.size()-1;i>=0;i--)
                {
                    if(v[i]<9)
                    {
                        v[i]++;
                        for(int j=i+1;j<v.size();j++)v[i]=0;
                        break;
                    }
                }
            }
            int start=0;
            if(dl>16)start=v.size()-6;
            if(dl>16)
            {
                p[++akt]=-1;
                //cout<<" ";
            }
            for(int i=start;i<v.size();i++)
            {
                p[++akt]=v[i];
                //cout<<p[akt];
            }
            ans=ans+dl-ile;
        }
        //cout<<endl;
        for(int i=1;i<=20;i++)
        {
            l[i]=p[i];
            //cout<<l[i]<<" ";
        }
        //cout<<endl<<dl<<endl<<endl;
        //cout<<endl;
    }
    cout<<ans<<endl;
}