题目描述

有 $N$ 个字符串排成一列，已知对于任意相邻的两个字符串，左边的字符串在字典序上都小于右边的字符串。也就是说，设第 $i$ 个字符串为 $S_i$，则有 $S_1 < S_2 < \cdots < S_N$（按字典序）。

已知 $S_i$ 的长度为 $A_i$，请你求出 $S_1, S_2, \ldots, S_N$ 中所有字符串可能包含的最小不同字符种类数。

输入格式

输入以如下格式从标准输入读入：

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

输出格式

输出所有字符串中可能包含的最小不同字符种类数。

样例 1

输入

3
3 2 1

输出

2

样例 2

输入

5
2 3 2 1 2

输出

2

说明/提示

限制条件

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

注意

字符串不一定要由英文字母组成。可以认为有无限多种字符，并且这些字符之间的字典序已经确定。

样例说明 1

例如，$S_1=$abc，$S_2=$bb，$S_3=$c 时，$S_1, S_2, \ldots, S_N$ 中包含的字符种类数为 $3$。但如果巧妙地选择字符串，可以将字符种类数降到 $2$。

由 ChatGPT 4.1 翻译