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
#include <iostream>
using namespace std;

long long add = 0, zeros = 0;

void printPrev(long long x) {
	cout << "TEST: " << x;
	
	long long mod = 0;
	if (add != 0) {
		mod = to_string(add).length();
	}
	
	for (int i = 0; i < zeros - mod; i++) {
		cout << "0";
	}
	if (add != 0) {
		cout << add;
	}
	cout << "\n";
}

int main() {
	long long prev, curr, result = 0;
	double ten[18] = {1, 10, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 
		1e9, 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17
	};
	int n;
	cin >> n;
	
	cin >> prev;
	
	for (int i = 1; i < n; i++) {
		cin >> curr;
		result += zeros;
		//printPrev(prev);
		
		long long prevLen = to_string(prev).length(), currLen = to_string(curr).length();
		if (prevLen + zeros < currLen) {
			// krotsze
			prev = curr;
			zeros = 0;
			add = 0;
		} else if (prevLen + zeros < 17) {
			long long calculatedPrev = prev * (long long)ten[zeros] + add;
			// cout << "calculatedPrev: " << calculatedPrev << "\n";
			
			if (calculatedPrev / ((long long)ten[prevLen + zeros - currLen]) < curr) {
				// wiekszy prefiksem - dodajemy zera
				// cout << "acha0!\n";
				prev = curr;
				zeros = prevLen + zeros - currLen;
				add = 0;
				continue;
			} else {
				// rowny lub mniejszy prefiksem
				if (prevLen + zeros == currLen) {
					// cout << "acha!\n";
					prev = curr;
					zeros = 1;
					add = 0;
					continue;
				} else {
					//cout << "acha2!\n";
					// prevLen + zeros > currLen
					long long rest = calculatedPrev %
						((long long)ten[prevLen + zeros - currLen]);
					if (to_string(rest + 1).length() > prevLen + zeros - currLen) {
						prev = curr;
						zeros = prevLen + zeros - currLen + 1;
						add = 0;
						continue;
					} else {
						// rest da sie zwiekszyc
						prev = curr;
						zeros = prevLen + zeros - currLen;
						add = rest + 1;
						continue;
					}
				}
			}
		} else {
			// prevLen + zeros >= 17
			long long calculatedPrev = prev * (long long)ten[12 - prevLen];
			
			if (calculatedPrev / ((long long)ten[to_string(calculatedPrev).length() - currLen]) < curr) {
				// wiekszy prefiksem - dodajemy zera
				prev = curr;
				zeros = prevLen + zeros - currLen + 1;
				add = 0;
				continue;
			} else {
				// prevLen + zeros > currLen
				prev = curr;
				zeros = prevLen + zeros - currLen;
				add += 1;
				continue;
			}
		}
	}
	result += zeros;
	//printPrev(prev);
	cout << result << "\n";
	
	return 0;
}