Suma de productes P43645

Donada una seqüència d’$n$ naturals, l’heu de transformar en una suma de productes, de manera que el resultat sigui el màxim possible. Teniu dues restriccions:

• No podeu modificar l’ordre relatiu dels elements.

• Cap producte pot tenir més de tres factors.

Per exemple, el màxim resultat per a la seqüència 20, 12, 7, 10, 12, 1, 10, 40, 8 és 5001, corresponent a $(20 \cdot 12 \cdot 7) + (10 \cdot 12) + 1 + (10 \cdot 40 \cdot 8)$.

Entrada

L’entrada consisteix en diversos casos, cadascun amb un nombre $n$, seguit d’$n$ naturals entre 1 i $10^4$. Podeu suposar $1 \le n \le 10^5$.

Sortida

Per a cada cas, escriviu el màxim resultat possible.