版权声明

本题版权归 Long Long OJ 所有。

注意

本题有弱化版 P36。

题目描述

给出一个有 $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]$，注意这并不是唯一的添加方案。

对于 $100\%$ 的数据：

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