Cerința

Avem un poligon convex cu n laturi, pe fiecare dintre cele n vârfuri fiind scris un număr natural. Acesta se împarte în n-2 triunghiuri. Definim valoarea unui triunghi produsul valorilor celor 3 vârfuri, iar valoarea poligonului este suma valorilor celor n-2 triunghiuri. Determinați valoarea maximă pe care o poate avea poligonul, împărțindu-l în mod optim.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații.

Date de ieșire

Programul va afișa pe ecran valoarea maximă a poligonului.

Restricții și precizări

• 1 ≤ n ≤ 250
• cele n numere citite vor fi mai mici decât 10.000

Exemplu:

Intrare

4
1 2 4 3

Ieșire

30

Explicație

Putem împărți poligonul în 2 moduri, cu valorile 20, respectiv 30.