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
#include <cstdio>
#include <stack>
using namespace std;
const int N = 213800;
int n;
int tab[N];
long long dp[N];
int dodatkowezera[N];
int sizeDec(long long a){
	int i = 0;
	while(a>0){
		a/=10;
		i++;
	}
	return i;
}

stack<int> rozklad(long long a){
	stack<int> q;
	while(a>0){
		q.push(a%10);
		a/=10;
	}
	return q;
}
int main(){
	//printf("%d\n",size(99));
	/*stack<int> q = rozklad(696969LL);
	while(!q.empty()){
		printf("%d",q.top());
		q.pop();
	}*/

	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		scanf("%d",&tab[i]);
	}
	dp[1] = tab[1];
	long long wynik = 0LL;
	for(int i=2; i<=n; i++){
		long long min = dp[i-1]+1;
		if((long long)tab[i]>=min){
			dp[i] = tab[i];
		}
		else{//zawsze ewentuialnie zostaje reszta z smin 
			long long temp = tab[i];//temp ma byc>=min
			stack<int> stemp = rozklad(temp);
			stack<int> smin = rozklad(min);
			bool dodajzero = false;
			bool tylesamozer = false;
			long long temp2 = 0;
			while(!stemp.empty() and !smin.empty()){//!stemp.empty powinno wystarczyc
				int t = stemp.top();
				stemp.pop();
				int m = smin.top();
				smin.pop();
				if(m>t){
					dodajzero = true;
					break;
				}
				else if(m<t){
					tylesamozer = true;
					break;
				}
			}
			dodatkowezera[i] = dodatkowezera[i-1];

			if(dodajzero || tylesamozer){
				//printf("dodajzero || tylesamozer\n");
				while(temp<min){
					temp*=10;
					if(temp>=1e16){
						//printf("CHUJ\n");
						if(dodajzero) dodatkowezera[i]++;
						temp/=10;
						break;
					}
				}
				dp[i] = temp;
			}
			else{
				dp[i] = min;
			}

		}
		//printf("%lld dod: %d\n",dp[i],dodatkowezera[i]);
		wynik+=sizeDec(dp[i])-sizeDec(tab[i])+dodatkowezera[i];

	}
	printf("%lld\n",wynik);
}