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
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <map>

using lint = long long int;

const int MAX_N = 200003;
int N;

lint a[MAX_N];
lint m_a[MAX_N];

lint left[MAX_N], right[MAX_N];
lint m_left[MAX_N], m_center[MAX_N], m_right[MAX_N];

lint result = 0;
lint sh[11];
std::map<lint, lint> mMap;

lint mOf(lint v) {
	return mMap.upper_bound(v)->second;
}

lint mFor(int i) {
	return m_left[i] + m_center[i] + m_right[i];
}

void fill0(int i, lint m0);
void add1(int i);

int main() {
	sh[0] = 1;
	for(int i = 1; i <= 10; ++i) {
		sh[i] = 10ll * sh[i-1];
		mMap[sh[i]] = i;
	}

	scanf("%d", &N);
	for(int i = 0; i < N; ++i) {
		scanf("%lld", &a[i]);
		m_a[i] = mOf(a[i]);
	}
	
	left[0] = a[0];
	m_left[0] = m_a[0];
	
	for(int i = 1; i < N; ++i) {
		int d = m_left[i-1] - m_a[i];
		int d_m_v = std::max(0, d);
		int d_m_u = std::max(0, -d);
		
		lint v = left[i-1] / sh[d_m_v];
		lint u = a[i] / sh[d_m_u];
		
		if(v < u) {
			fill0(i, mFor(i-1));
		} else if(v > u) {
			fill0(i, mFor(i-1)+1);
		} else {
			if(d_m_u > 0) {
				fill0(i, mFor(i-1));
			} else {
				left[i] = left[i-1];
				right[i] = right[i-1];
				m_left[i] = m_left[i-1];
				m_center[i] = m_center[i-1];
				m_right[i] = m_right[i-1];

				add1(i);
			}
		}
		
		result += (mFor(i) - m_a[i]);
	}
	
	printf("%lld\n", result);
    return 0;
}

void fill0(int i, lint m0) {
	lint d0 = std::max(0ll, m0 - m_a[i]);
	lint d_e = m_a[i] + d0;
	
	if(d_e > 9) {
		left[i] = a[i] * sh[9-m_a[i]];
		m_left[i] = 9;
		if(d_e > 18) {	
			m_right[i] = 9;
			m_center[i] = d_e - 18;
		} else {
			m_right[i] = d_e - 9;
		}
	} else {
		left[i] = a[i] * sh[d_e-m_a[i]];
		m_left[i] = d_e;
	}
}

void add1left(int i);
void add1right(int i);
void add1(int i) {
	if(m_center[i] == 0) {
		if(m_right[i] == 0) {
			add1left(i);
		} else {
			add1right(i);
		}
	}
}

void add1left(int i) {
	if((left[i]+1) % sh[m_left[i] - m_a[i]] == 0ll) {
		fill0(i, mFor(i)+1);
	} else {
		if(++left[i] % sh[m_left[i]] == 0ll) {
			++m_left[i];
		}
	}
}

void add1right(int i) {
	if(++right[i] % sh[m_right[i]] == 0ll) {
		right[i] = 0ll;
		add1left(i);
	}
}