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
#include <string>
#include <cstdio>
#include <cstdlib>


using namespace std;

string num[200005];
unsigned long long result;

// ###################### String comparisons
bool lt(const string &s1, const string &s2)
{
    if(s1.size() < s2.size()) return true;
    else if(s1.size() > s2.size()) return false;
    else return s1 < s2;
}
bool ht(const string &s1, const string &s2)
{ return lt(s2, s1); }
bool eq(const string &s1, const string &s2)
{ return !lt(s1, s2) && !ht(s1, s2); }
bool he(const string &s1, const string &s2)
{ return ht(s1, s2) || eq(s1, s2); }
bool le(const string &s1, const string &s2)
{ return lt(s1, s2) || eq(s1, s2); }

// ######################## BigNum math

string bignum_sum(const string &s1, const string &s2)
{
    string result;
    int temp = 0, store = 0, carry = 0;
    int size_diff = s1.size() - s2.size();

    for (int i = s1.size() - 1; i > -1; i--) {
        if (i - size_diff < 0)
            temp = int(s1[i] - '0') + carry;
        else
            temp = int(s1[i]-'0') + int(s2[i - size_diff]-'0') + carry;
        store = temp % 10;
        carry = temp / 10 % 10;
        result = to_string(store) + result;
    }
    if (carry != 0) result = to_string(carry) + result;

    return result;
}

string sum(const string &s1, const string &s2)
{
    if(ht(s1, s2)) return bignum_sum(s1, s2);
    else return bignum_sum(s2, s1);

}

// ########################## Binary searches
int BSdigitnum(const string &prev, const string &curr)
{
    int low = 1, high = 200100, mid;
    while(low <= high)
    {
        mid = (low+high)/2;
        if(lt(prev, curr+string(mid, '9')) && he(prev, curr+string(mid-1, '9'))) break;
        if(he(prev, curr+string(mid, '9'))) low = mid + 1;
        else if(lt(prev, curr+string(mid-1, '9'))) high = mid - 1;
    }

    return mid;
}


int main()
{
    int size = 0;
    scanf("%d", &size);
    for(int i = 0; i < size; ++i)
    {
        int a;
        scanf("%d", &a);
        num[i] = to_string(a);
    }

    string prev, curr = num[0];
    for(int i = 1; i < size; ++i)
    {
        prev = curr; curr = num[i];
        if(lt(prev, curr))
        {
            // printf("******* SKIP!!! %s - %s\n", prev.c_str(), curr.c_str());
            continue;
        }
        int digit_num = BSdigitnum(prev, curr);
        result += digit_num;
        // printf("Lowest possible: %s - %s = ", prev.c_str(), curr.c_str(), digit_num);
        if(ht(curr+string(digit_num, '0'), prev)) curr += string(digit_num, '0');
        else curr = sum(prev, "1");
        //curr = BSadddigit(prev, curr, digit_num);
        // printf("%d\n", digit_num);
    }
    printf("%llu\n", result);

    return 0;
}