Se citesc n baloane asezate la rand, fiecare cu o valoare. Cand se sparge balonul de pe pozitia i, se castiga a[stanga]*a[i]*a[dreapta] monede, unde stanga si dreapta sunt cele mai apropiate baloane INCA nesparte de o parte si de alta a lui i (sau valoarea 1, daca nu mai exista niciun balon nespart in acea directie). Determinati, folosind Programarea Dinamica, numarul maxim de monede ce pot fi obtinute spargand toate baloanele, in ordinea optima.
- Date de intrare
- Pe prima linie se citeste n. Pe a doua linie se citesc cele n valori ale baloanelor.
- Date de iesire
- Se afiseaza un singur numar: numarul maxim de monede obtinute.
- Restrictii
- 1 <= n <= 100, 0 <= valoare <= 100
Exemple
Exemplul 1
Intrare
4 3 1 5 8
Iesire
167
Exemplul 2
Intrare
1 5
Iesire
5