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
139
140
141
142
143
144
#include <iostream>
#include <map>
#include <vector>
#include <memory.h>

using namespace std;

const int LIMIT=9+6;	// 9 cyfr na limit z zadania <=10^9 oraz 6 dla zapisania wartości 0-200000.


int convert(int val, char* d) {
    static const int BUF_LEN=19;
    static char buf[BUF_LEN+1];

    int pos=BUF_LEN;
    if(val==0) {
        d[0]='0';
        d[1]='\0';
        return 1;
    } else {
        while(val>0) {
            buf[--pos]=(char)('0'+(val%10));
            val/=10;
        }
    }

    const int len=BUF_LEN-pos;

    for(int i=0;i<len;++i) {
        d[i]=buf[i+pos];
    }
    d[len]='\0';

    return len;
}



/** Klasa reprezentująca liczbę */
class Number {
    friend ostream& operator<<(ostream& str, const Number& n);
private:
    /** Długość części zapisanej w d */
	int l;
	/** Początkowe cyfry wartości liczby zapisane odwrotnie */
	char d[LIMIT+1];
	/** Ilość dalszych (mało istotnych) cyfr liczby */
	int e;
public:
	Number(int v) {
		l=convert(v, d);
		e=0;
	}
	Number(const Number& src) {
		e=src.e; l=src.l; memcpy(d,src.d, sizeof(d));
	}
public:
	// Pomocnicza funkcja zwraca cyfrt dla danej liczby
	inline char operator[](int pos) const { 
		if(pos<e) return '0';
		pos-=e;
		if(pos>=l) return ' ';
		return d[pos]; 
	}

	/** Liczba cyfr w tej liczbie */
	inline int digits() const { return l+e; }

	Number& operator=(const Number& src) { e=src.e; l=src.l; memcpy(d, src.d, sizeof(d)); return *this; }

	/** Pomocnicza funkcja, która zwiększą tą wartość o zadaną liczbę cyfr - mnożenie przez 10^t */
	void pow10(int t) {
		const int loc=min(t, LIMIT-l);	// ile lokalnej zmiany
		for(int i=0;i<loc;++i) d[l++]='0';	// dodajemy lokalne zera
		e+=t-loc;		// dodajemy globalne zera
	}

	/** Wykonuje operację z zadania - zwieksza liczbę, aby była mniejsza niż zadana w argumencie */
	int nextAfter(const Number& min) {
		int dif=min.digits()-digits();	// jest na odwrót, bo chcemy mieć dodatnią liczbę gdy mniejsza
		if(dif<0) return 0;	// jeżeli ta liczba ma więcej cyfr, to z definicji jest większa - koniec
		const int c=l;	// długość wejścowej liczby - tego nie będziemy zmieniac
		if(dif>0) {	// jeżeli ta ma mniej cyfr, to należy wyrównać ich ilość
			pow10(dif);	// uzupełniamy, aby liczby bły równe, co do długości
		}
		for(int i=0;i<c;++i) {
			int cmp=d[i]-min.d[i];
			if(cmp>0) return dif;	// na stałym elemencie jest większa koniec
			if(cmp<0) {	// na stałym elemencie jest mniejsza, trzeba zwiększyć o rząd
				pow10(1);
				return dif+1;	// to koniec, bo liczba dłuższa, więc zera pozostają
			}
		}
		if(dif==0) {	// jeżeli nic nie dodano to koniec
			pow10(1);
			return 1;
		}
		// stała cześć taka sama, więc sprawdzamy, czy dodana cześć może być większa, czyli czy min na tej pozycji to nie same 9-tki
		bool canIncrease=false;
		for(int i=c;i<l;++i) {
			if(min.d[i]!='9') {
				canIncrease=true;
				break;
			}
		}
		if(!canIncrease) {
			pow10(1);
			return dif+1;
		}
		int acc=1;
		for(int i=l-1;i>=c;--i) {
			char v=min.d[i]+(char)acc;
			if(v>'9') {
				v='0'; acc=1;
			} else acc=0;
			d[i]=v;
		}

		return dif;
	}
};


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;

	int64_t sum=0;
	// aktualna liczba, dla której poszukujemy większej; na starcie 0, bo i tak wartości wejściowe zaczynają się od 1.
	Number current(0);
	for(int i=0;i<n;++i) {
		int v;
		cin>>v;
		Number now(v);

		sum+=now.nextAfter(current);
		current=now;
	}
	cout<<sum<<endl;
	
	return 0;
}