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
#include <bits/stdc++.h>
using namespace std;
#define pr if(0)
#ifndef LOCAL
#define pr if(0)
#endif
const int MAXN = 2e5+69;
using ll = long long int;
ll t, pt, pot[19], n, w;
int c, pb, b, cp;
inline void ss() {
	t = b = 0;
	while (c < '0' || c > '9')
		c = getchar();

	while (c >= '0' && c <= '9') {
		t = t * 10 + c - '0';
		c = getchar();
	}
}
#ifdef LOCAL
bool curp = false;
char ss_[2][2000000];
void p() {
	char *ss = ss_[curp];
	curp ^= 1;
	sprintf(ss, "%lld", t);
	int l = strlen(ss);
	for (int i = 0; i < b; i++) {
		ss[l++] = '0';
	}
	ss[l] = 0;
	for (int ccp = cp; ccp > 0; ccp /= 10) {
		ss[--l] = '0' + (ccp%10);
	}
	fprintf(stdout, "%s\n", ss);
}
#endif
int main() {
	scanf("%lld", &n);
	pot[0] = 1;
	for (int i = 1; i < 19; i++)
		pot[i] = pot[i-1] * 10;

	ss();

#ifdef LOCAL
	pr p();
	pr printf("pierwsza liczba %lld ma dopisane %d zer\n", t, b);
#endif
	for (int i = 1; i < n; i++) {
		pt = t; pb = b;
		ss();
		pr fprintf(stdout, "______ %d  %lld\n", i, t);
		while (pt < t && pb > 0) {
			pt *= 10;
			pb--;
			if (pb < 18) {
				pt += cp / pot[pb];
				cp %= pot[pb];
			}
		}

		int mpot = 0;
		while (t * pot[mpot] + pot[mpot] - 1 < pt)
			mpot++;

		pr printf("pt: %lld, t*pot: %lld\n", pt, t*pot[mpot]);
		b = pb + mpot;
		if (mpot && t * pot[mpot] <= pt) {
			pr printf("assert %lld >= %lld\n", t*pot[mpot] + pot[mpot]-1, pt);
			assert(t*pot[mpot] + pot[mpot] -1 >= pt);
			if (b < 18)
				cp += (pt % pot[mpot]) * pot[pb] + 1; // tutaj jest rozpatrzony przypadek kiedy t jest prefixem pt
			else {
				t = pt;
				b -= mpot;
			}
		}
		w += pb + mpot;

		if (b < pb) {
			w += pb - b;
			b = pb;
		}
		pr printf("t=%lld, b=%d, pt=%lld, pb=%d, cp=%d\n", t, b, pt, pb, cp);
		if (t == pt) // przypadek kiedy t jest prefixem pt jest rozpatrzony wyzej 
			cp++;

		if (b < 18 && cp >= pot[b]) {
			assert(cp == pot[b]);
			cp = 0;
			b++;
			w++;
		}
		while (t % 10 == 0) {
			b++;
			t /= 10;
		}

#ifdef LOCAL
		pr p();
		pr assert(strlen(ss_[curp]) < strlen(ss_[!curp]) || strcmp(ss_[curp], ss_[!curp]) < 0);
		pr printf("liczba %lld ma dopisane %d zer [%d]\n", t, b, cp);
#endif
	}
	printf("%lld\n", w);
}