2x1 versión Difícil
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 enteros positivos , cada uno en el rango . 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 s adyacentes con un ). 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 , y las siguientes líneas dan la sucesión de 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 , y luego ella combina los s en un . Note que no es óptimo unir los dos primeros s.
Comments