Se consideră un șir de numere naturale a[1], a[2], …, a[n]. Asupra șirului efectuăm n operații. O operație constă din eliminarea unuia din numerele de la capetele șirului. Deci la primul pas se elimină fie a[1], fie a[n]. Dacă la pasul i se elimină elementul a[k], atunci costul eliminării este i * a[k].

Cerința

Să se determine costul maxim posibil total al celor n operații.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi pe următoarele n linii se citește câte un număr din șir.

Date de ieșire

Programul va afișa pe ecran un singur număr natural reprezentând costul maxim total posibil al eliminării celor n numere din șir.

Restricții și precizări

• 1 ≤ n ≤ 2000
• 1 ≤ a[i] ≤ 1000

Exemplu:

Intrare

4
3
2
4
1

Ieșire

29

Explicație

La primul pas se elimină 1 (costul 1 * 1), la pasul doi se elimină 3 (cost 2 * 3), la pasul al treilea se elimină 2 (cost 3 * 2), iar la ultimul pas se elimină 4 (cost 4 * 4). Costul total maxim va fi 1+6+6+16=29.