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.

Constraints

For $70\%$ of the test cases:

• $1 \leq n \leq 10^4$.
• $1 \leq a_i \leq 10^9$.
• Score: $210$ pts.

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

• $1 \leq n \leq 10^5$.
• All the numbers in $a$ are equal.
• Score: $90$ pts.

Input

The input is given in the following format from the standard input:

$n\\a_1\\a_2\\:\\a_n$

Output

Output the minimum number of digits to be added.

Sample Input

4
20
1
45
132

Sample Output

4

Explanation

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

Note that this is not the only possible solution.