Appending Digits for a Strictly Increasing Sequence

This problem is translated from PA 2018 Round 2 (Nowy kontrakt).

You are given a sequence of positive integers \(a_1, a_2, \ldots, a_N\). You are allowed to append digits to the end of any number. Appending a digit \(t\) (where \(t \in \{0,1,2,3,4,5,6,7,8,9\}\)) to a number \(a\) transforms it according to the formula:

[ a \gets a \times 10 + t ]

Your goal is to modify the sequence so that it becomes strictly increasing while minimizing the total number of digits appended. Note that you may leave a number unchanged if it already satisfies the condition relative to the previous number.

inputFormat

The input begins with an integer \(N\) (the length of the sequence). The next line contains \(N\) positive integers \(a_1, a_2, \ldots, a_N\), separated by spaces.

It is guaranteed that all values are positive integers.

outputFormat

Output a single integer denoting the minimum total number of digits that must be appended to make the sequence strictly increasing.

sample

4
1 2 3 4

0