← 返回题目列表

AtCoder · agc029_c

C. 词典编排限制

中文机器翻译题面 查看原题

分数: 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