4) For the following problem, write a program (in as close to Java code -but doesnt need to be compilable/runnable code, ie no English explanation vague pseudocode and all helper methods must be defined).

+--------------------------+

A few years ago, 2048 was a popular game to download and play on smartphone. You don't need to know anything about 2048, but here is a different game called 248. In 248, the game starts with a sequence of N integers where N is between 2 and 248 (inclusive) and each integer in the sequence is between 1 and 40 (inclusive). To play the game, the player must select two adjacent integers with equal values and replace them with a single integer of value one greater. For example, two adjacent 3's can be replaced with 4. After repeatedly doing combination operations there will eventually be no more equal adjacent numbers in the sequence and the game is then done. The score at the end of a game is whatever number is largest in the final sequence. Write a program to find the largest possible score.

--INPUT--

The input will be N+1 integers separated by whitespace. The first integer gives the value of N, the number of integers in the sequence. The following N integers give the sequence of the N integers at the beginning of the game.

--OUTPUT--

A single integer: the largest possible number remaining in the sequence after any sequence of legal combination operations.

Sample Input Sample Output

4 5

3

3

3

4