Descripción

Hay una pila de ~N~ cartas, cada una de ellas tiene un número no-negativo escrito. El entero escrito en la ~i-~ésima carta desde arriba es ~A_i~.

Eduardo va a realizar la siguiente operación hasta que queden dos cartas en la pila:

• Escoger tres cartas consecutivas de la pila.
• Eliminar la carta del medio de las tres.
• Por cada una de las dos cartas restantes, reemplaze el número escrito en ellas por la suma de ese número y el número escrito en la carta eliminada.
• Devolver las dos cartas a sus posiciones originales en la pila, sin intercambiar sus posiciones.

Calcula la mínima suma posible de los enteros escritos en las últimas dos cartas restantes.

Entrada

La primera línea de la entrada contiene un entero ~N~ (~2 \le N \le 18~).

Las siguiente línea contiene ~N~ enteros ~A_i~ (~0 \le A_i \le 10^9~).

Salida

Imprime una línea con la mínima suma posible de los enteros escritos en las últimas dos cartas restantes.

Subtareas

• Subtarea 1: ~2 \le N \le 10~ (~8~ puntos)
• Subtarea 2: Para todo ~i~ se garantiza que ~A_i = i~ (~8~ puntos)
• Subtarea 3: Para todo par (~i, j~) se garantiza que ~A_i = A_j~ (~12~ puntos)
• Subtarea 4: Para todo ~i~ se garantiza que ~A_i \in \{0,1\}~ (~12~ puntos)
• Subtarea 5: Para todo ~i~ se garantiza que ~0 \le A_i \le 500~ (~20~ puntos)
• Subtarea 6: Sin restricciones adicionales (~40~ puntos)

Ejemplos

Entrada 1

4
3 1 4 2

Salida 1

16

Podemos minimizar la suma de los enteros escritos en las últimas dos cartas restantes haciendo lo siguiente:

• Inicialmente los enteros escritos en las cartas son ~3, 1, 4, 2~.
• Escogemos la primera, la segunda y la tercera carta. Eliminamos la segunda carta, que tiene ~1~ escrito en ella, adicionamos ~1~ a las dos cartas restantes, y devolvemos las cartas en su orden original. Los enteros escritos en las cartas ahora son ~4, 5, 2~
• Escogemos la primera, la segunda y la tercera carta. Eliminamos la segunda carta, que tiene un ~5~ escrito en ella, adicionamos ~5~ a las dos cartas restantes, y devolvemos las cartas en su orden original. Los enteros escritos en las cartas ahora son ~9, 7~.
• La suma de los enteros escritos en las cartas es ~16~.

Entrada 2

6
5 2 4 1 6 9

Salida 2

51

Entrada 3

10
3 1 4 1 5 9 2 6 5 3

Salida 3

115

Notas

Notar que las cartas que se escojan no tienen por qué ser necesariamente las primeras en la pila de cartas (aunque si tienen que ser consecutivas). En el primer ejemplo se puede hacer lo siguiente:

• Escogemos la segunda, la tercera y la cuarta carta. Eliminamos la tercera carta, que tiene ~4~ escrito en ella, adicionamos ~4~ a las dos cartas restantes, y devolvemos las cartas en su orden original. Los enteros escritos en las cartas ahora son ~3, 5, 6~.
• Escogemos la primera, la segunda y la tercera carta. Eliminamos la segunda carta, que tiene ~5~ escrito en ella, adicionamos ~5~ a las dos cartas restantes, y devolvemos las cartas en su orden original. Los enteros escritos en las cartas ahora son ~8, 11~.
• La suma de las dos cartas restantes es ~8 + 11 = 19~, lo cual no mejora la mínima suma que es ~16~.