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
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
  
long long alpha, e, space, alphaprim, my_limit, n, result;
vector<long long> a;

long long base(long long num) {
  long long base = 1000000;

  while (base > num) base /= 10;
  if (base == 0) base = 1;

  while (base <= num) base *= 10;

  return base / 10;
}

long long my_rank(long long num) {
  long long res = 0;
  while (num > 0) {
    num /= 10;
    res++;
  }
  return res;
}

void kernel(long long cur) {
  // alpha >= cur
  if (cur > alpha) { 
    result += e;
    alpha = cur;
    return;
  }
  long long base_alpha, base_cur, ap;
  base_alpha = base(alpha);
  base_cur = base(cur);
  ap = alpha / (base_alpha / base_cur);

  if (ap < cur) {
    alpha = cur * base_alpha / base_cur;

    int zeros = my_rank(base_alpha) - my_rank(base_cur) + e;
    space = zeros > 6 ? 1000000 : pow(10, zeros) - 1;
  }
  else if (ap == cur) {
    if (e == 0 || space == 0) {
      alpha++;
      int new_ap = alpha / (base(alpha) / base_cur);
      if (ap != new_ap) {
        alpha--;
        alpha = cur * 10 * base_alpha / base_cur;
      }
      if (alpha >= my_limit) {
        alpha /= 10;
        e++;
      }
      int zeros = my_rank(base_alpha) - my_rank(base_cur) + e;
      space = zeros > 6 ? 1000000 : pow(10, zeros) - 1;
    }
    else if (space > 0)
      space--;
  }
  else { // ap > cur
    alpha = cur * base_alpha * 10 / base_cur;
    if (alpha >= my_limit) {
      alpha /= 10;
      e++;
    }
    int zeros = my_rank(base_alpha) - my_rank(base_cur) + e;
    space = zeros > 6 ? 1000000 : pow(10, zeros) - 1;
  }

  result += my_rank(base(alpha)) - my_rank(base_cur) + e;
}

void solve() {
  for (int i = 1; i < n; i++) 
    kernel(a[i]);
}

int main() {

  cin >> n;
  a.resize(n);

  for (int i = 0; i < n; i++)
    cin >> a[i];

  alpha = a[0];
  e = space = result = 0;
  my_limit = 100000000000;

  solve();
  cout << result;
}