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

using namespace std;

enum ComparisonResult
{
    LESS,
    EQUAL,
    GREATER
};

struct Comparison
{
    ComparisonResult result;
    bool equalDigitsCount;
    
    Comparison(ComparisonResult res, bool eqDigitsCount)
    {
        result = res;
        equalDigitsCount = eqDigitsCount;
    }
};

Comparison compareNumbers(const string& a, const string& b)
{
    if (a.length() < b.length())
        return Comparison(LESS, false);
    else if (a.length() > b.length())
        return Comparison(GREATER, false);
        
    for (unsigned int i = 0; i < a.length(); ++i)
    {
        if (a[i] < b[i])
            return Comparison(LESS, true);
        else if (a[i] > b[i])
            return Comparison(GREATER, true);
    }
    return Comparison(EQUAL, true);
}

unsigned int transformToMinGreaterNumber(string& currNum, const string& prevNum, const Comparison& comparison)
{    
    if (comparison.result == EQUAL)
    {
        currNum += '0';
        return 1;
    }
    
    // currNum < prevNum
    if (comparison.equalDigitsCount)
    {
        currNum += '0';
        return 1;
    }
    
    // currNum has less digits than prevNum
    unsigned int appendedDigitsCount = prevNum.length() - currNum.length();

    auto mispair = mismatch(currNum.begin(), currNum.end(), prevNum.begin());
    if (mispair.first != currNum.end())
    {
        if (*mispair.first < *mispair.second)
            ++appendedDigitsCount;

        currNum.append(appendedDigitsCount, '0');
        return appendedDigitsCount;
    }

    // currNum and prevNum have same prefix
    unsigned int prefixLen = currNum.length(), i = prevNum.length() - 1;
    bool greater = false;
    
    currNum = prevNum;
    while (!greater)
    {
        // can't change constant prefix
        if (i < prefixLen)
            break;
        
        if (currNum[i] == '9')
            --i;
        else
        {
            currNum[i] += 1;
            greater = true;
            
            for (++i; i < currNum.length(); ++i)
                currNum[i] = '0';
        }
    }
    
    if (!greater)
    {
        for (i = prefixLen; i < currNum.length(); ++i)
            currNum[i] = '0';
        currNum += '0';
        ++appendedDigitsCount;
    }
    
    return appendedDigitsCount;
}

int main()
{
    ios_base::sync_with_stdio(false);
    
    unsigned int n, i;
    string previousNumber, currentNumber;
    unsigned long long int result = 0;
    
    cin >> n;
    cin >> previousNumber;
    for (i = 1; i < n; ++i)
    {
        cin >> currentNumber;

        Comparison comparison = compareNumbers(currentNumber, previousNumber);
        if (comparison.result != GREATER)
            result += (unsigned long long int) transformToMinGreaterNumber(currentNumber, previousNumber, comparison);
        
        previousNumber = currentNumber;
    }
    
    cout << result << "\n";

    return 0;
}