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

long long int maxSmallNumber = 1000000000LL * 100000000LL; // 10^9 * 10^8
long long int totalDigits = 0;

long long int powerOfTen[18] = {
	1LL,
	10LL,
	100LL,
	1000LL,
	10000LL,
	100000LL,
	1000000LL,
	10000000LL,
	100000000LL,
	1000000000LL,
	10000000000LL,
	100000000000LL,
	1000000000000LL,
	10000000000000LL,
	100000000000000LL,
	1000000000000000LL,
	10000000000000000LL,
	100000000000000000LL
};

// return number of digits of a number
int numberLength(long long int n) {
	int length = 0;
	while(n > 100000) {
		n /= 100000;
		length += 5;
	}
	while(n > 0) {
		n /= 10;
		length++;
	}
	return length;
}

// true if n2 is prefix of n1
// assume n1 > n2
bool isPrefixLL(long long int n1, long long int n2){
	int len1 = numberLength(n1);
	int len2 = numberLength(n2);
	int lendiff = len1 - len2;
	long long int shortN1 = n1 / powerOfTen[lendiff];
	return shortN1 == n2;
}

// return the lowest number higher than n1 that has n2 as its prefix
long long int nextWithPrefixLL(long long int n1, long long int n2){
	int len1 = numberLength(n1);
	int len2 = numberLength(n2);
	int lendiff = len1 - len2;
	
	
	if (n2 > n1) {
		return n2;
	}
	if (isPrefixLL(n1, n2)) {
		n2 *= powerOfTen[lendiff];
		totalDigits += lendiff;
		long long int numdiff = n1 - n2;
		long long int newnumdiff = numdiff + 1;
		int nxlen = numberLength(newnumdiff);
		if (nxlen > lendiff) {
			n2 *= 10;
			totalDigits++;
		} else {
			n2 += newnumdiff;
		}
		return n2;
	} else {
		n2 *= powerOfTen[lendiff];
		totalDigits += lendiff;
		if (n1 > n2) {
			n2 *= 10;
			totalDigits++;
		}
		return n2;
	}
}

long long int expandToFullNumber(long long int n){
	int length = numberLength(n);
	totalDigits += 10-length;
	return n * powerOfTen[10-length];
}

int n, k;
long long int lastSmallValue = 0;
long long int lastBase = 0;
bool smallMode = true;
int breakIndex = -1;
int currentLength = 0;
long long int newBase = 0;

int main(){
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &k);
		lastSmallValue = nextWithPrefixLL(lastSmallValue, k);
		if (lastSmallValue >= maxSmallNumber) {
			breakIndex = i;
			currentLength = 18;
			break;
		}
	}
	
	if(breakIndex == -1){
		printf("%lld\n", totalDigits);
		return 0;
	}
	
	lastBase = lastSmallValue / 100000000LL; // CUT TO 10 DIGITS
	
	for (int i = breakIndex + 1; i < n; ++i) {
		scanf("%d", &k);
		bool prefixize = isPrefixLL(lastBase, k);
		if(prefixize){
			// just add zeros to the current length
			int length = numberLength(k);
			totalDigits += currentLength - length;
		} else {
			newBase = expandToFullNumber(k);
			if(newBase < lastBase){
				currentLength++;
			}
			totalDigits += currentLength - 10;
			lastBase = newBase;			
		}
	}
	printf("%lld\n", totalDigits);
	return 0;
}