[AdditionalFile2417.zip](file://AdditionalFile2417.zip?type=additional_file)

#2417. 「USACO 2016 US Open, Platinum」262144

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 USACO 2016 US Open Contest, Platinum Problem 1. 262144

Bessie 正在玩一个游戏，规则如下。
开始时有一个 $N$ 个正整数的数列，每个数在 $1$ 到 $40$ 之间。
每次操作，Bessie 可以把两个相邻且相同的数替换成比他们值大 $1$ 的数，例如两个相邻的 $7$ 替换成 $8$。当无法再合并时，游戏结束。游戏目标是使游戏结束时数列中的最大值尽可能大。
请帮助 Bessie 找出最大值。

输入格式

第一行一个数 $N$。
接下来 $N$ 行每行一个数，表示初始值。

输出格式

输出最大值。

样例

输入

4
1
1
1
2

输出

3

合并第二、第三个 $1$，数列变为 $1\:\:2\:\:2$；再合并两个 $2$ 就可以得到 $3$。 注意，合并前两个 $1$ 并非最优解。

数据范围与提示

$2 \le N \le 262144,$ 数列中每个数在 $1$ 到 $40$ 之间。