Source

This problem is moved from Long Long OJ (Copyright by Google Inc.). All rights reserved.

Adapted from: https://luogu.com.cn/problem/P13026

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 \le n \le 10^3$.
• $1 \le a_i \le 10^9$.

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

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