Hay \(n\) globos en fila con números \(a_0, \dots, a_{n-1}\). Al reventar el globo \(i\) ganas \(\text{izq} \cdot a_i \cdot \text{der}\), donde \(\text{izq}\) y \(\text{der}\) son los números de sus vecinos actuales (los que siguen sin reventar); si no tiene vecino de un lado, ese factor vale \(1\). Después, sus dos vecinos quedan adyacentes. Revienta todos los globos en el orden que más gane y di cuánto ganas.

Entrada

La primera línea tiene \(n\) \((1 \le n \le 300)\). La segunda tiene los \(a_i\) \((0 \le a_i \le 100)\).

Salida

La mayor ganancia total.

Ejemplo 1

Entrada

4
3 1 5 8

Salida

167

Ejemplo 2

Entrada

2
1 5

Salida

10

Ejemplo 3

Entrada

1
7

Salida

7