问题描述

有$N$个字符串按顺序排列在一行。已知对于任意相邻的两个字符串，左边的字符串在字典序上小于右边的字符串。即，字典序有$S_1<S_2<...<S_N$成立，其中$S_i$是从左边数第$i$个字符串。

如果已知$S_i$的长度为$A_i$，那么$S_1,S_2,...,S_N$中至少包含多少个不同的字符？

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• $A_i$是整数。

注意

字符串不一定由英文字母组成；可能包含任意多个不同的字符（并且对这些字符定义了字典序）。

输入

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

$N$ $A_1$ $A_2$ $...$ $A_N$

输出

打印字符串中包含的不同字符的最少可能数量。

样例输入 1

3
3 2 1

样例输出 1

2

当$S_1=$abc，$S_2=$bb和$S_3=$c时，$S_1,S_2,...,S_N$中包含的不同字符数量为$3$。

但是，如果我们合理选择字符串，不同字符的数量可以为$2$。

样例输入 2

5
2 3 2 1 2

样例输出 2

2