分数: 700 点
问题陈述
有 N 字符串排列成一行。 众所周知,对于任何两个相邻的字符串,左侧的字符串按字典顺序小于右侧的字符串。 也就是说, S_1<S_2<...<S_N 按字典顺序成立,其中 S_i 是 i从左边算起第一个字符串。
中至少包含多少个不同的字符 S_1,S_2,...,S_N,如果长度 S_i 已知是 A_i?
约束
- 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,S_2,...,S_N 将是 3 ,例如, S_1=abc, S_2=bb 和 S_3=c.
但是,如果我们正确选择字符串,不同字符的数量可以是 2.
示例输入 2
5 2 3 2 1 2
示例输出 2
2