有一组正整数数据，现对这组数据按照如下操作：

1. 从这组数中找出两个相邻且相同的数，删掉其中一个数，剩下的一个数加1（例如：两个相邻的6，变成一个7）；
2. 重复操作第1步，直到这组数据中没有相邻且相同的数时，操作结束。

现给定N（1≤N≤2000）个正整数，表示这一组数，请问按照要求操作结束后，这组数据中最大的数是多少。

注意：不同的操作方式得到的最后结果不同，要求最后的结果是所有操作方式中最大的。

示例说明

当N=6，这组数为 1、2、2、2、3、4时：

• 可获得最大结果的操作如下： 第一次操作：将这组数据中后两个相邻的2，变成3，此时这组数变为1，2，3，3，4； 第二次操作：将这组数据中两个相邻的3，变成4，此时这组数变为1，2，4，4； 第三次操作：将这组数据中两个相邻的4，变成5，此时这组数变为1，2，5； 此时没有相邻相同数，操作结束，最大数为5。
• 非最大结果的操作如下： 第一次操作：将这组数据中前两个相邻的2，变成3，此时这组数变为1，3，2，3，4； 此时没有相邻相同数，操作结束，最大数为4。

因此最终可获得的最大数是5。

输入描述

第一行输入一个正整数N（1≤N≤2000） 第二行输入N个正整数（1≤正整数≤40），相邻两个数之间以一个空格隔开

输出描述

输出一个正整数，表示所有操作方式中最大的结果

样例输入

6
1 2 2 2 3 4

样例输出

5