版权声明

本题版权归 Long Long OJ 所有。

注意

本题有加强版 P78。

题目描述

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

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

求最少添加几个数字。

输入格式

第一行一个正整数 $n$。

下面 $n$ 行，每行一个正整数 $a_i$。

输出格式

输出添加数字最小个数。

样例

4
20
1
45
132

4

提示

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

对于 $70\%$ 的数据：

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

对于另外 $30\%$ 的数据：

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