版权声明

本题版权归 Long Long OJ 所有。

注意

本题有弱化版：

题目描述

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

数据范围

对于 $50\%$ 的数据，$n \le 15$。

对于 $100\%$ 的数据，$1 \le n \le 10^6$，$1 \le a_i \le 10^9$。