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

using namespace std;

const int MAX_I = 1000000000;

int previous_number[15], current_number[15];
int n, previous_length, current_length;
char word[15];
long long int result;

int ten_exp(int number) {
  if (number > 9) {
    return MAX_I;
  }
  int result = 1;
  while (number > 0) {
    result *= 10;
    --number;
  }
  return result - 1;
}

int main() {
  scanf("%d", &n);
  scanf("%s", word);
  previous_length = int(strlen(word));
  for (int i = 0; i < previous_length; ++i) {
    previous_number[i] = int(word[i]) - 48;
  }
  for (int i = 1; i < n; ++i) {
    scanf("%s", word);
    current_length = int(strlen(word));
    for (int j = 0; j < current_length; ++j) {
      current_number[j] = int(word[j]) - 48;
    }
    if (previous_length < current_length) {
      previous_length = current_length;
      for (int j = 0; j < 10; ++j) {
        previous_number[j] = current_number[j];
      }
      continue;
    } else if (previous_length == current_length) {
      bool need_to_add = true;
      for (int j = 0; j < current_length; ++j) {
        if (previous_number[j] < current_number[j]) {
          need_to_add = false;
          break;
        } else if (current_number[j] < previous_number[j]) {
          break;
        }
      }
      if (need_to_add) {
        ++result;
        ++previous_length;
      }
      for (int j = 0; j < 10; ++j) {
        previous_number[j] = current_number[j];
      }
    } else {
      bool equal_prefix = true;
      for (int j = 0; j < current_length; ++j) {
        if (previous_number[j] < current_number[j]) {
          result += previous_length - current_length;
          equal_prefix = false;
          for (int j = 0; j < 10; ++j) {
            previous_number[j] = j < current_length ? current_number[j] : 0;
          }
          break;
        } else if (current_number[j] < previous_number[j]) {
          equal_prefix = false;
          ++previous_length;
          result += previous_length - current_length;
          for (int j = 0; j < 10; ++j) {
            previous_number[j] = j < current_length ? current_number[j] : 0;
          }
          break;
        }
      }
      if (equal_prefix) {
        if (previous_length > 10 && previous_number[10] == -1) {
          for (int j = 9; j >= 0; --j) {
            if (previous_number[j] != 9) {
              ++previous_number[j];
              break;
            } else {
              previous_number[j] = 0;
            }
          }
          if (previous_number[0] == 0) {
            previous_number[0] = 1;
            ++previous_length;
          }
          result += previous_length - current_length;
        } else if (previous_length > 10 && previous_number[10] == 0) {
          previous_number[10] = ten_exp(previous_length - 10);
          result += previous_length - current_length;
        } else if (previous_length > 10 && previous_number[10] > 0) {
          result += previous_length - current_length;
          if (--previous_number[10] == 0) {
            previous_number[10] = -1;
          }
        } else {
          bool need_to_add = false;
          for (int j = previous_length - 1; j >= current_length; --j) {
            if (previous_number[j] != 9) {
              ++previous_number[j];
              break;
            } else {
              if (j == current_length) {
                need_to_add = true;
              }
              previous_number[j] = 0;
            }
          }
          if (need_to_add) {
            ++previous_length;
          }
          result += previous_length - current_length;
        }
      }
    }
  }
  printf("%lld\n", result);
  return 0;
}