Escógelo

Submit solution
Points: 100 (partial)
Time limit: 3.0s
Memory limit: 64M
Author:
raikiri
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Tú estás jugando el juego de la selección. Tienes una lista de números enteros positivos y tienes permitido seleccionar cualquier número que no sea el primero o el último en esta lista. Cuando tú seleccionas un número, ese número es eliminado de la lista, y tu puntuación se incrementa en la suma del número seleccionado con sus vecinos (números adyacentes).

Por ejemplo, si la lista contiene 1 2 3 4 5, y seleccionas 3, tu puntuación sería 2+3+4=9. En el siguiente turno, tu lista sería 1 2 4 5, y si seleccionas 4 ahora, tu puntuación sería 9+2+4+5 = 20, quedándote la lista 1 2 5. El juego termina cuando solo quedan dos números.

Dado una lista de números, ¿cuál es la máxima puntuación que puedes obtener?

Entrada

La entrada consistirá en un número n (3 \le n \le 200) que es la cantidad de números en la lista, seguido por n números k_1 k_2... k_n y cada número k_i satisface 1 \le k_i \le 100.

Salida

Imprima la máxima puntuación.

Ejemplo de entrada:

5 
1 2 3 4 5

Ejemplo de salida:

30

Comments