В ряд расположены n шариков. На i-м шарике написано число a_i.

Шарики нужно лопнуть по одному, в некотором порядке. Когда лопают шарик i, игрок получает число монет, равное произведению значений на самом шарике и на двух его ближайших ещё не лопнутых соседях слева и справа.

Если слева или справа подходящего соседа нет, то вместо его значения используется 1.

После того как шарик лопнут, оставшиеся шарики сдвигаются по смыслу: его бывшие соседи становятся соседями друг для друга.

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

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

Первая строка содержит одно целое число n — количество шариков.

Вторая строка содержит n целых чисел a_i — значения, написанные на шариках.

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

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

Ограничения

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

Ответ может не помещаться в 32-битный целочисленный тип.

Примеры

Пример 1

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

1
7

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

7

Пример 2

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

3
1 0 2

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

4