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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int SIGNIFICANT_DIGITS = 17; const ll INF = (1ll<<60);
int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	vector <ll> A(n); vector <string> S(n);
	for (int i = 0; i < n; i++) {
		cin >> A[i];
		S[i] = to_string(A[i]);
	}
	vector <int> Ans(n, 0), Dig(n, 0); vector <ll> B(n, INF); 
	int cmp;
	B[0] = A[0];
	Dig[0] = S[0].size();
	for (int i = 1; i < n; i++) {
		if (S[i-1] == S[i]) {			// S[i-1] == S[i]
			if (Dig[i-1] >= SIGNIFICANT_DIGITS) {
				Dig[i] = Dig[i-1];
				Ans[i] = Dig[i] - S[i].size();
			}
			else
			if (to_string(B[i-1] + 1).substr(0, S[i].size()) == S[i]) {
				B[i] = B[i-1] + 1;
				Dig[i] = Dig[i-1];
				Ans[i] = Dig[i] - S[i].size();
			}
			else {
				B[i] = A[i];
				while (B[i] <= B[i-1]) {
					B[i] *= 10;
					Ans[i]++;
				}
				Dig[i] = to_string(B[i]).size();
			}
		}
		else
		if (S[i-1].size() < S[i].size() && S[i].substr(0, S[i-1].size()) == S[i-1]) {	// S[i-1] in S[i]
			if (Dig[i-1] >= SIGNIFICANT_DIGITS) {
					Dig[i] = Dig[i-1];
					Ans[i] = Dig[i] - S[i].size();
				}
			else
			if (to_string(B[i-1] + 1).substr(0, S[i].size()) == S[i]) {
				B[i] = B[i-1] + 1;
				Dig[i] = Dig[i-1];
				Ans[i] = Dig[i] - S[i].size();
			}
			else {
				B[i] = A[i];
				while (B[i] <= B[i-1]) {
					B[i] *= 10;
					Ans[i]++;
				}
				Dig[i] = to_string(B[i]).size();
			}
		}
		else
		if (S[i-1].size() > S[i].size() && S[i-1].substr(0, S[i].size()) == S[i]) {		// S[i] in S[i-1]
			if (Dig[i-1] >= SIGNIFICANT_DIGITS) {
					Dig[i] = Dig[i-1];
					Ans[i] = Dig[i] - S[i].size();
				}
			else
			if (to_string(B[i-1] + 1).substr(0, S[i].size()) == S[i]) {
				B[i] = B[i-1] + 1;
				Dig[i] = Dig[i-1];
				Ans[i] = Dig[i] - S[i].size();
			}
			else {
				B[i] = A[i];
				while (B[i] <= B[i-1]) {
					B[i] *= 10;
					Ans[i]++;
				}
				Dig[i] = to_string(B[i]).size();
			}
		}
		else {
			cmp = S[i-1].compare(S[i]);
			if (cmp > 0) {			// S[i-1] > S[i] && S[i-1][j] > S[i][j]
				if (Dig[i-1] >= SIGNIFICANT_DIGITS) {
					Dig[i] = Dig[i-1]+1;
					Ans[i] = Dig[i] - S[i].size();
				}
				else {
					B[i] = A[i];
					while (B[i] <= B[i-1]) {
						B[i] *= 10;
						Ans[i]++;
					}
					Dig[i] = to_string(B[i]).size();
				}
			}
			else 
			if (cmp < 0) {	// S[i-1] < S[i] && S[i-1][j] < S[i][j]
				if (Dig[i-1] >= SIGNIFICANT_DIGITS) {
					Dig[i] = Dig[i-1];
					Ans[i] = Dig[i] - S[i].size();
				}
				else {
					B[i] = A[i];
					while (B[i] <= B[i-1]) {
						B[i] *= 10;
						Ans[i]++;
					}
					Dig[i] = to_string(B[i]).size();
				}
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i < n; i++)
		ans += Ans[i];
	cout << ans <<endl;
	return 0;
}