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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int duzo = 200007, malo = 15;
int ilema[duzo], iledod[duzo];
int pocz[duzo][malo], kon[duzo][malo];
int poprz[2 * malo];

int buduj_poprz(int i) {
  int ind = 0;
  for(int k = 0; k < ilema[i - 1]; ++k) {
    poprz[ind] = pocz[i - 1][k];
    ++ind;
  }
  for(int k = iledod[i - 1] - 1; k >= 0; --k) {
    poprz[ind] = kon[i - 1][k];
    ++ind;
  }
  return ind;
}

int laduj(int a, int i) {
  stack<int> cyfry;
  while(a > 0) {
    cyfry.push(a % 10);
    a /= 10;
  }
  int ilecyfr = 0;
  while(!cyfry.empty()) {
    pocz[i][ilecyfr] = cyfry.top();
    cyfry.pop();
    ++ilecyfr;
  }
  ilema[i] = ilecyfr;
}

void dodaj1(int i) {
  int c = 0;
  while(kon[i - 1][c] == 9) {
    kon[i - 1][c] = 0;
    ++c;
  }
  ++kon[i - 1][c];
}

int ile_dod(int i) {
  if(i == 1) return 0;
  int ilecyfr = ilema[i], ilestary = ilema[i - 1] + iledod[i - 1];
  int rowne = 0, dod, iledp = iledod[i - 1], ind, zmniejsz = 0;
  if(iledp >= malo) {
    for(int c = 0; c < min(ilecyfr, ilema[i - 1]) && !rowne; ++c) {
      if(pocz[i - 1][c] < pocz[i][c]) rowne = -1;
      else if(pocz[i - 1][c] > pocz[i][c]) rowne = 1;
    }
    if(ilecyfr > ilema[i - 1] && !rowne) rowne = -1;
  }
  else {
    ind = buduj_poprz(i);
    for(int c = 0; c < min(ilecyfr, ind) && !rowne; ++c) {
      if(poprz[c] < pocz[i][c]) rowne = -1;
      else if(poprz[c] > pocz[i][c]) rowne = 1;
    }
  }
  if(rowne == -1) dod = max(ilestary - ilecyfr, 0);
  else if(rowne == 1) dod = max(ilestary - ilecyfr + 1, 0);
  else {
    if(ilestary < ilecyfr) return 0;
    dod = ilestary - ilecyfr;
    if(iledp >= malo) {
      dodaj1(i);
      for(int k = ilecyfr; k < ilema[i - 1]; ++k) {
        pocz[i][k] = pocz[i - 1][k];
        ++zmniejsz;
      }
      ilema[i] = max(ilema[i - 1], ilema[i]);
    }
    else {
      ind = buduj_poprz(i);
      int pierw = -1;
      for(int k = ind - 1; k >= 0 && pierw == -1; --k) {
        if(poprz[k] != 9) pierw = k;
      }
      if(pierw < ilecyfr) ++dod;
      else {
        ++poprz[pierw];
        for(int k = pierw + 1; k < ind; ++k) poprz[k] = 0;
        for(int k = ind - 1, c = 0; c < dod; ++c) {
          kon[i][c] = poprz[k];
          --k;
        }
        for(int k = ilecyfr; k < ilema[i - 1]; ++k) {
          pocz[i][k] = poprz[k];
          ++zmniejsz;
        }
        ilema[i] = max(ilema[i - 1], ilema[i]);
      }
    }
  }
  iledod[i] = dod - zmniejsz;
  return dod;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, rob;
  cin >> n;
  ll wyn = 0;
  for(int i = 1; i <= n; ++i) {
    cin >> rob;
    laduj(rob, i);
    wyn += (ll)ile_dod(i);
  }
  cout << wyn;
  return 0;
}