Your video game production company has achieved stunning success – a series of $N$ games about a quasar slayer traveling through the Galaxy sold excellently, bringing you fame, money, and unexpected trouble. News has broken that a famous science-fiction writer, whose books your games are based on, has decided that he sold the adaptation rights for too low a price and, through his lawyers, is demanding a change to the contract terms.*

The contract stipulated that for licensing game number $i$ (where $i = 1, 2, \dots, N$), the writer would receive a payment $a_i$, which is a positive integer. However, the lawyers argue that since each subsequent game sold better than the previous one, the payment should also be higher. You want to avoid unnecessary publicity (as well as panic among shareholders), so the interference with the contract terms should be as minimal as possible. You have therefore decided to append a certain number of digits to the end of each of the numbers $a_1, \dots, a_N$ such that the resulting new sequence is strictly increasing. For each $a_i$, the appended digits (and their count) can be different, and you may also choose not to change some numbers at all.

Determine the minimum total number of digits you must append to achieve this.

Input

The first line of the input contains a single integer $N$ ($1 \le N \le 200\,000$). The following $N$ lines contain the integers $a_1, \dots, a_N$ ($1 \le a_i \le 10^9$).

Output

Your program should output a single integer – the minimum possible number of appended digits.

Examples

Input 1

3
8
5
13

Output 1

2

Note

Explanation for the example: By appending the digits 7 and 3 to the second and third numbers respectively, we obtain the strictly increasing sequence $(8, 57, 133)$. Other solutions are possible, but it is impossible to achieve the goal by appending only one digit.

*Rumor has it that he will spend the profit on purchasing a mithril fishing vest – however, this information could not be confirmed at the source.