您的游戏制作公司取得了巨大的成功——系列游戏《银河夸克毁灭者》销量极佳，为您带来了名声、财富，以及意想不到的麻烦。有消息称，为您游戏提供原著的著名科幻作家认为他出售的改编权价格过低，正通过律师要求修改合同条款。

合同规定，对于第 $i$ 款游戏（其中 $i = 1, 2, \dots, N$），作家将获得报酬 $a_i$，这是一个正整数。然而，律师们辩称，既然每一款后续游戏的销量都比前一款好，那么报酬也应该更高。为了避免不必要的轰动（以及股东们的恐慌），您希望对合同条款的改动尽可能小。因此，您决定在每个数字 $a_1, \dots, a_N$ 的末尾添加若干位数字，使得最终得到的序列严格递增。对于每个 $a_i$，添加的数字（以及添加的位数）可以不同，您也可以选择不对某些数字进行任何修改。

请计算为了达到这一目标，总共最少需要添加多少位数字。

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 200\,000$)。接下来的 $N$ 行中，每行包含一个整数 $a_i$ ($1 \le a_i \le 10^9$)。

输出格式

输出一个整数，表示最少需要添加的数字位数。

样例

输入 1

3
8
5
13

输出 1

2

说明 1

通过分别在第二个数和第三个数后添加数字 $7$ 和 $3$，我们可以得到一个严格递增序列 $(8, 57, 133)$。虽然可能存在其他方案，但无法通过仅添加一位数字来实现目标。