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
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <string>

class Number
{
public:
    std::string value = "0";

public:
    Number(std::string init = "0") : value(init) {}

    void append(std::string sufix)
    {
        value += sufix;
    }

    friend std::ostream& operator<< (std::ostream &out, const Number &number)
    {
        return out << number.value;
    }

    friend std::istream& operator>> (std::istream &in, Number &number)
    {
        return in >> number.value;
    }

    std::pair<size_t, const std::string&> key() const
    {
        return {value.size(), value};
    }

    size_t size() const { return value.size(); }
    void pop() { value.pop_back(); }
    
    friend bool operator< (const Number &lhs, const Number &rhs) { return lhs.key() < rhs.key(); }
    friend bool operator<= (const Number &lhs, const Number &rhs) { return lhs.key() <= rhs.key(); }

    friend bool operator>= (const Number &lhs, const Number &rhs) { return lhs.key() >= rhs.key(); }

    void operator++ ()
    {
        auto it = std::prev(value.end());

        while (*it == '9') {

            *it = '0';

            /*if (it == value.begin())
            {
                value = "1" + value;
                return;
            }*/

            --it;
        }

        *it += 1;
    }
};

void test()
{
    using namespace std;

    int n;
    cin >> n;

    vector<Number> input(n);
    copy_n(istream_iterator<Number>(cin), n, input.begin());

    long long answer = 0;
    long long zeros = 0;
    Number previous = {"0"};

    for (const Number &prefix : input)
    {
        Number low = prefix;
        Number high = prefix;

        while (previous >= high)
        {
            answer += 1;
            low.append("0");
            high.append("9");
        }

        answer += zeros;

        constexpr int MAX_LENGTH = 20;

        if (low.size() > MAX_LENGTH)
        {
            //if (previous.size() != MAX_LENGTH) throw std::logic_error("Incorrect previous size");

            low.pop();
            high.pop();

            zeros += 1;

            previous = {"0"};
        }

        if (low <= previous)
        {
            low = previous;
            ++low;
        }

        previous = low;
    }

    cout << answer << endl;
}

int main()
{   
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    test();
    return 0;
}