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
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pii;
typedef vector<int> vi;

int compare(string &a1, string &prev_a) {
	for (unsigned i = 0; i < prev_a.size(); ++i) {
		if (i < a1.size()) {
			if (a1[i] > prev_a[i])
				return 1;
			else if (a1[i] < prev_a[i])
				return -1;
		}
		else {
			if (prev_a[i] < '9')
				return 0;
		}
	}	
	return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
	
	int n;
	cin >> n;
	vi arr(n);
	for (int &i : arr)
		cin >> i;
	
	string prev_a = to_string(arr[0]);
	int k = 0;
	unsigned m = prev_a.size();
	long long res = 0;
	//cerr << '\n' << prev_a << endl;
	//string debug = prev_a;
	for (unsigned i = 1; i < arr.size(); ++i) {
		string a1 = to_string(arr[i]);
		
		if (a1.size() > prev_a.size()) {
			k = 0;
			prev_a = a1;
		}
		else {
			int cmp_res = compare(a1, prev_a);
			if (cmp_res != 0) {
				//wyzeruj k, liczba tej samej dlugosci
				for (unsigned i = prev_a.size() - k; i < prev_a.size(); ++i) {
					prev_a[i] = '0';
				}
				k = 0;
				
				if (cmp_res < 0) 
					prev_a += '0';
				
				//przepisz liczbe
				for (unsigned i = 0; i < max(m, static_cast<unsigned>(a1.size())); ++i) {
					if (i < a1.size())
						prev_a[i] = a1[i];
					else
						prev_a[i] = '0';
				}
			}
			else {
				//zwieksz k
				++prev_a.back();
				k = max(k, 1);
				for (int i = prev_a.size() - 1; prev_a[i] > '9'; --i) {
					prev_a[i] = '0';
					++prev_a[i - 1];
					k = max(k, static_cast<int>(prev_a.size() - i));
				}
				if (m > a1.size())
					k = min(15, static_cast<int>(prev_a.size() - a1.size()));
			}
		}
		m = a1.size();
		res += prev_a.size() - a1.size();

		//if (prev_a.size() < debug.size() || (prev_a.size() == debug.size() && debug > prev_a)) {
			//cerr << i - 1 << " " << debug << endl;
			//cerr << i << " " << prev_a << endl;
			//break;
		//}
		//debug = prev_a;
		//cerr << prev_a << " k: " << k << endl;
	}
	
	cout << res << '\n';
    return 0;
}