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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
#include <stdio.h>
#include <vector>
#include <string>
#include <algorithm>
#include <sstream>

using namespace std;

#define LL long long
#define MAX_LEN 200010
#define DBG(X) 

LL MAX_VAL = 10e15;

LL a[MAX_LEN];

inline LL count_digits(LL a) {
  LL res = 0;
  while (a) {
    a /= 10;
    ++res;
  }
  return res;
}

inline void fill_with_digits(char* arr, int* cnt, LL val) {
  *cnt = 0;
  while (val) {
    arr[(*cnt)++] = val % 10;
    val /= 10;
  }
}

inline LL increase_digits(LL a, LL b, LL max_allowed) {
  char arr_a[32];
  char arr_b[32];
  int arr_a_cnt;
  int arr_b_cnt;
  fill_with_digits(arr_a, &arr_a_cnt, a);
  fill_with_digits(arr_b, &arr_b_cnt, b);
  if (arr_a_cnt != arr_b_cnt) {
    printf("ERROR: sizes don't match\n");
  }
  bool already_larger = false;
  for (int i=0; i < max_allowed; i++) {
    if (already_larger) {
      if (arr_a[i] < arr_b[i]) {
        arr_a[i] = arr_b[i];
      }
      continue;
    }
    if (arr_b[i] == 9) {
      continue;
    }
    arr_a[i] = arr_b[i] + 1;
    already_larger = true;
  }
  LL res = 0;
  for (int i=arr_a_cnt-1; i >=0; i--) {
    res *= 10;
    res += arr_a[i];
  }
  return res;
}

inline LL next_best2(LL prev, LL *curr) {
  DBG(printf("next_best2(%lld, %lld)\n", prev, *curr)); 
  LL curr_local = * curr;
  if (curr_local > prev) {
    return 0;
  }
  LL c0val = curr_local;
  LL c9val = curr_local;
  LL c0_added_cnt = 0;
  LL c9_added_cnt = 0;
  while (c0val <= prev) {
    c0val *= 10;
    ++c0_added_cnt;
  }
  while (c9val <= prev) {
    c9val = c9val * 10 + 9;
    ++c9_added_cnt;
  }
  if (prev + 1 == c0val) {
    *curr = c0val;
    return c0_added_cnt;
  }
  if (c0_added_cnt == 1) {
    *curr = c0val;
    return 1;
  }
  DBG(printf("c9_added_cnt=%lld, c0_added_cnt%lld\n", c9_added_cnt, c0_added_cnt));
  if (c9_added_cnt == c0_added_cnt) {
    *curr = c0val;
    return c0_added_cnt;
  } else { // c9_added_cnt < c0_added_cnt
    DBG(printf("c9 < c0\n"));
    c0val /= 10;
    --c0_added_cnt;
    *curr = increase_digits(c0val, prev, c0_added_cnt);
    return c0_added_cnt;
  }
}


struct BigNum {
  LL original_value_;
  LL value_;
  int additional_zeroes_;

  int added_digits_;
  bool overflow_;

  BigNum(LL value, int additional_zeroes, int added_digits) {
    original_value_ = value;
    value_ = value;
    additional_zeroes_ = additional_zeroes;
    added_digits_ = added_digits;
    normalize();
  }

  static int compare(const BigNum &a, const BigNum &b) {
    int aL = a.length();
    int bL = b.length();
    if (aL < bL) {
      return -1;
    } else if (aL > bL) {
      return 1;
    } else {
      // additional zeroes are above 10^15 only!!
      if (a.value_ < b.value_) return -1;
      else if (a.value_ == b.value_) return 0;
      else return 1;
    }
  }

  int length() const {
    return count_digits(original_value_) + additional_zeroes_;
  }

  bool operator>(const BigNum &b) {
    return compare(*this, b) == 1;
  }

  void normalize() {
    while (value_ >= MAX_VAL) {
      value_ /= 10;
      additional_zeroes_++;
    }
    overflow_ = (additional_zeroes_ > 0);
  }

  string str() {
    ostringstream osstream;
	  osstream	<< "{v:" << value_ << ", added: " << added_digits_ << ", zeroes: " << additional_zeroes_ << "}";
    return osstream.str();
  }
};


BigNum next_best3(BigNum &prev_big, BigNum &curr_big) {
  DBG(printf("next_best3 %s, %s\n", prev_big.str().c_str(), curr_big.str().c_str()));
  if (curr_big > prev_big) {
    return curr_big;
  }
  if (!prev_big.overflow_) {
    LL prev = prev_big.value_;
    LL curr = curr_big.value_;
    int d_added = next_best2(prev, &curr);
    return BigNum(curr, 0, d_added);
  }
  else {
    DBG(printf("Overflow!\n"));
    LL prev = prev_big.value_;
    LL curr = curr_big.value_;
    int d_added = next_best2(prev, &curr) + prev_big.additional_zeroes_;
    return BigNum(curr, prev_big.additional_zeroes_, d_added);
  }
}




LL solve(int n) {
  LL res = 0;

  BigNum prev_big(a[0], 0, 0);
  for (int i=1; i < n; i++) {
    BigNum curr_big(a[i], 0, 0);
    BigNum next_big = next_best3(prev_big, curr_big);
    DBG(printf("a[%d]=%s (res=%lld)\n", i, next_big.str().c_str(), res));
    res += next_big.added_digits_;
    prev_big = next_big;
  } 
  return res;
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i=0; i < n; i++) { 
    int ai;
    scanf("%d", &ai);
    a[i] = ai;
  }

  printf("%lld\n", solve(n));
  return 0;
}