Problem Description

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

You are given a sequence $a$ of $N$ positive integers. You need to make the sequence strictly increasing by appending digits to the end of numbers in the sequence. Your goal is to minimize the number of appended digits.

Appending a digit $t$ to a number $a$ means:

$a \gets a \times 10 + t$, where $t \in \{0,1,2,3,4,5,6,7,8,9\}$.

Input Format

The first line contains an integer $N$, the length of the sequence.

Lines $2$ to $N + 1$ each contain one number. Line $i$ contains the $(i - 1)$-th number in the sequence.

Output Format

Print one integer: the minimum number of operations.

3
8
5
13

2

Hint

Sample 1 Explanation

Append one digit to the 2nd number and one digit to the 3rd number, i.e., $a_2 \gets a_2 \times 10 + 7$, $a_3 \gets a_3 \times 10 + 3$. The new sequence becomes $(8,57,133)$, which is strictly increasing. The number of operations is $2$. There are other ways with $2$ operations, but there is no way with only $1$ operation.

Constraints

This problem uses bundled tests.

For $100\%$ of the testdata:

• $1 \le N \le 200000$.
• $1 \le a_i \le 10^9$.

Translated by ChatGPT 5