2x1 versión Difícil


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
C, C++, Go, Java, Python, VB

A Bessie le gusta bajar juegos para su télefono celular, aunque sin embargo ella no encuentra cómoda la pequeña pantalla táctil para usarla con sus pezuñas grandes. Ella está particularmente intrigada por el juego actual que ella está jugando.

El juego comienza con una sucesión de N enteros positivos (2 \leq N \leq 262144), cada uno en el rango 0\ldots40. En un movimiento, Bessie puede tomar dos números adyacentes con valores iguales y los reemplaza con un solo número de valor uno más grande (por ejemplo, ella podría reemplazar dos 7s adyacentes con un 8). El objetivo es tratar de maximizar el valor del número más grande que ella pueda crear.

¡Por favor ayude a Bessie a obtener el puntaje tan alto como sea posible!

Entrada

La primera línea de la entrada contiene N, y las siguientes N líneas dan la sucesión de N números al comienzo del juego.

Salida

Por favor, dé como salida el mayor entero que Bessie puede generar.

Ejemplo de entrada

4
1 
1
1
2

Ejemplo de salida

3

En el ejemplo mostrado, Bessie primero combina el segundo y el tercero para obtener la sucesión 1\,2\,2, y luego ella combina los 2s en un 3. Note que no es óptimo unir los dos primeros 1s.


Comments

There are no comments at the moment.