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 <bits/stdc++.h>
using namespace std;


int n, dopisano[200111], dl[200111];
long long t[200111];
long long wynik;

int liczbaCyfr(long long w) {
	int res = 0;
	while(w > 0) {
		res++;
		w /= 10;
	}
	return res;
}

int aktWiekszaLeksy(long long pop, long long akt) {
	vector<int> vPop, vAkt;
	while(pop > 0) {
		vPop.push_back(pop%10);
		pop /= 10;
	}
	while(akt > 0) {
		vAkt.push_back(akt%10);
		akt /= 10;
	}
	while(!vPop.empty() && !vAkt.empty()) {
		if(vPop.back() > vAkt.back()) return -1; 	//poprzednia leksykograficznie wieksza
		if(vPop.back() < vAkt.back()) return 1;		//aktualna leksykograficznie wieksza
		vPop.pop_back();
		vAkt.pop_back();
	}
	return 0;										//aktualna prefixem poprzedniej
}

void dopiszZera(int in, int doDopisania) {
	long long akt = t[in];
	dopisano[in] = doDopisania;
	int lc = liczbaCyfr(akt);
	while(doDopisania > 0) {
		if(lc < 17) {
			akt *= 10;
			lc++;
		}
		else {
			dl[in] = doDopisania;
			break;
		}
		doDopisania--;
	}
	t[in] = akt;
}

bool nieSameDziewiatki(int in) {
	int ileMogeZmienic = liczbaCyfr(t[in]) - liczbaCyfr(t[in+1]);
	long long liczba = t[in];
	if(ileMogeZmienic > 15) ileMogeZmienic = 15;
	while(ileMogeZmienic > 0) {
		if(liczba%10 < 9) return true;
		ileMogeZmienic--;
		liczba /= 10;
	}
	return false;
}

void dopiszWieksze(int in) {
	int ileDopisano = liczbaCyfr(t[in-1]) - liczbaCyfr(t[in]) + dl[in-1];
	long long liczba = t[in-1];
	liczba++;
	t[in] = liczba;
	dl[in] = dl[in-1];			//tyle samo zer powyżej ~10^18
	dopisano[in] = ileDopisano;
}



int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &t[i]);		
	}
	
	for(int i = 2; i <= n; i++) {
		int lcl = liczbaCyfr(t[i-1]), lca = liczbaCyfr(t[i]);
		if(lcl < lca) { 	//aktualna liczba jest dłuższa od poprzedniej, więc jest większa
			continue;
		}
		
		if(lcl == lca) {	//aktualna liczba jest równie długa co poprzednia
			if(t[i] > t[i-1]) {					//aktualna liczba jest większa od poprzedniej, zostawiam
				continue;
			}
			if(t[i] <= t[i-1]) {				//aktualna liczba jest mniejsza lub równa poprzedniej
				t[i] *= 10;
				dopisano[i] = 1;
				continue;
			}
		}
		
							//aktualna liczba jest krótsza niż poprzednia
		int leks = aktWiekszaLeksy(t[i-1], t[i]);			
		if(leks == 1) {				//aktualna jest leksykograficznie większa, wypełniam zerami do równej długości
			int doDopisania = lcl - lca + dl[i-1];
			dopiszZera(i, doDopisania);
			continue;
		}
		if(leks == 0) {				//aktualna jest prefiksem poprzedniej, 
			if(nieSameDziewiatki(i-1)) {		//jeśli dopisane do poprzedniej cyfry są różne od dziewiątek, to zwiększam 
				dopiszWieksze(i);
				
			}
			else {								//w przeciwnym wypadku dodaję same zera aby uzyskać dłuższą liczbę
				int doDopisania = lcl - lca + dl[i-1] + 1;
				dopiszZera(i, doDopisania);
			}
			continue;
		}
									//aktualna jest leksykograficznie mniejsza, wypełniam zerami żeby była dłuższa o 1
		int doDopisania = lcl - lca + dl[i-1] + 1;
		dopiszZera(i, doDopisania);
		
	}
	
	
	for(int i = 1; i <= n; i++) wynik += dopisano[i];
	printf("%lld\n", wynik);
	
}