题目描述

给定一个长度为 $n$ 的正整数序列。

每次操作可以选择两个相邻且相等的数，将它们合并成一个比原数大 $1$ 的数。例如，可以将两个相邻的 $7$ 合并成一个 $8$。

合并后，序列长度减少 $1$。可以进行任意次操作，也可以不再操作。请你求出最终序列中能够出现的最大数值。

输入格式

第一行输入一个整数 $n$，表示序列长度。

接下来 $n$ 行，每行输入一个整数 $a_i$，表示序列中的第 $i$ 个数。

输出格式

输出一个整数，表示最终序列中能够出现的最大数值。

样例 1

4
1
1
1
2

3

样例说明

一种最优操作顺序为：

1 1 1 2
→ 1 2 2
→ 1 3

先合并中间两个 $1$，再合并两个 $2$，最终得到 $3$。

数据范围

对于所有测试数据：

• $1\le n\le248$；
• $1\le a_i\le40$。

评分说明

测试组	分值	额外限制
1	20 分	$n\le10$
2	30 分	$n\le80$
3	50 分	无额外限制