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
#include <iostream>
#include <string>
#include <cstdint>
#include <algorithm>

const int MAX_NUMBER_COUNT = 200000;

int main() {

	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	int N;
	std::cin >> N;

	int newNumber;
	std::cin >> newNumber;
	std::string lastNumberStr = std::to_string(newNumber);
	int lastNumberBaseEnd = lastNumberStr.size();
	int lastNumberZeroesEnd = lastNumberStr.size();
	lastNumberStr.reserve(MAX_NUMBER_COUNT);

	long long int newDigitsCount = 0;


	for (int i = 1; i < N; ++i) {
		
		std::cin >> newNumber;
		std::string newNumberStr = std::to_string(newNumber);

		if (newNumberStr.size() < lastNumberStr.size() 
			|| (newNumberStr.size() == lastNumberStr.size() 
				&& newNumberStr <= lastNumberStr.substr(0, newNumberStr.size()))) {

			bool newBeginningLower = newNumberStr < lastNumberStr.substr(0, newNumberStr.size());
			int currentNewDigits = 0;

			if (newBeginningLower) {
				currentNewDigits = lastNumberStr.size() - newNumberStr.size() + 1;
				lastNumberBaseEnd = newNumberStr.size();
			} else if (newNumberStr == lastNumberStr.substr(0, newNumberStr.size())) {
				bool couldIncrease = false;
				int numberEnd = 0;
				for (auto it = lastNumberStr.rbegin(); !couldIncrease && it != lastNumberStr.rend()-newNumberStr.size(); ++it) {
					if (lastNumberZeroesEnd > lastNumberBaseEnd && it == lastNumberStr.rend() - lastNumberZeroesEnd) {
						couldIncrease = true;
						numberEnd = lastNumberStr.rend() - it;
						(*it) = '1';
					} else if ((*it) != '9') {
						couldIncrease = true;
						numberEnd = lastNumberStr.rend() - it;
						(*it)++;
					} else (*it) = '0';
				}
				if (couldIncrease) {
					currentNewDigits = lastNumberStr.size() - newNumberStr.size();
					lastNumberBaseEnd = numberEnd;
				} else {
					currentNewDigits = lastNumberStr.size() - newNumberStr.size() + 1;
					lastNumberBaseEnd = newNumberStr.size();
				}
			} else {
				currentNewDigits = lastNumberStr.size() - newNumberStr.size();
				lastNumberBaseEnd = newNumberStr.size();
			}

			std::copy(newNumberStr.begin(), newNumberStr.end(), lastNumberStr.begin());
			newDigitsCount += currentNewDigits;
			lastNumberZeroesEnd = newNumberStr.size() + currentNewDigits;
			lastNumberStr.resize(newNumberStr.size() + currentNewDigits);
			if (lastNumberBaseEnd < 10 && lastNumberZeroesEnd > lastNumberBaseEnd)
				std::fill(lastNumberStr.begin() + lastNumberBaseEnd, lastNumberStr.begin() + lastNumberZeroesEnd, '0');
			
		} else {
			lastNumberStr.resize(newNumberStr.size());
			std::copy(newNumberStr.begin(), newNumberStr.end(), lastNumberStr.begin());
		}

	}

	std::cout << newDigitsCount << "\n";

	return 0;
}