题目描述

给出一个有 $n$ 个整数的序列 $a$，你需要在整数末尾添加数字，使得序列严格单调递增。

给一个数 $x$ 末尾添加数字 $t$（$0\le t\le 9$），即 $x\leftarrow x\times10+t$。

求最少添加几个数字。

约束条件

对于 $70\%$ 的数据：

• $1\le n\le 10^4$；
• $1\le a_i\le10^9$；
• 得 $210$ 分。

对于 $30\%$ 的数据：

• $1\le n\le 10^5$；
• $a$ 中数都相等；
• 得 $90$ 分。

输入

输入以以下格式从标准输入给出：

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

输出

输出添加数字最小个数。

样例输入

4
20
1
45
132

样例输出

4

样例解释

添加数字后 $a=[20,199,459,1329]$，注意这并不是唯一的添加方案。