Пиротехник подготовил n воздушных шаров, подвешенных в один ряд. На i-м шаре написано число a_i.

Пиротехник лопает шары по одному в произвольном порядке и получает выручку. Если в некоторый момент лопается шар i, то за него начисляется left * a_i * right, где:

• left — число на ближайшем еще не лопнувшем шаре слева;
• right — число на ближайшем еще не лопнувшем шаре справа.

Если слева или справа такого шара нет, вместо соответствующего значения считается 1.

Требуется определить максимальную суммарную выручку, которую можно получить, выбрав оптимальный порядок лопания шаров.

Входные данные

В первой строке дано целое число n — количество шаров.

Во второй строке записаны n целых чисел a_1, a_2, ..., a_n — числа на шарах.

Выходные данные

Выведите одно целое число — максимальную суммарную выручку.

Ограничения

• 1 <= n <= 500
• 0 <= a_i <= 100

Ответ может быть большим, поэтому для промежуточных вычислений рекомендуется использовать 64-битный целочисленный тип.

Примеры

Пример 1

Входные данные

4
3 1 5 8

Выходные данные

167

Пояснение

При подходящем порядке лопания максимальная выручка равна 167 монетам.

Пример 2

Входные данные

1
0

Выходные данные

0

Пример 3

Входные данные

5
1 100 1 0 0

Выходные данные

300