Source

This problem is adapted from Long Long OJ. All rights reserved.

Attention

is the hard version of this problem.

Problem Description

Given a sequence $a$ of $n$ integers, you need to add digits at the end of the integers in order to make the sequence strictly increasing.

Adding digit $t$ ($0\le t\le 9$) at the end of a number $x$ can be represented as $x\leftarrow x\times10+t$.

Find the minimum number of digits to be added.

Input Format

The first line consists of an integer $n$.

The following $n$ lines consists of $n$ integers $a_1,a_2,\ldots,a_n$.

Output Format

Output the minimum number of digits to be added.

Samples

4
20
1
45
132

4

Sample Explanation

After adding digits, the sequence becomes $a=[20,199,459,1329]$.

Note that this is not the only possible solution.

Data Range

For $70\%$ of the test cases:

• $1 \leq n \leq 10^3$.
• $1 \leq a_i \leq 10^9$.

For the remaining $30\%$ of the test cases:

• $1 \leq n \leq 10^5$.
• All the numbers in $\bm a$ are equal.
• $1 \leq a_i \leq 10^9$.