В лаборатории готовят длинную цепочку матричных преобразований. Лаборанту нужно перемножить матрицы A_1 · A_2 · ... · A_n, но порядок расстановки скобок можно выбрать разными способами.

Матрица A_i имеет размер p_{i-1} x p_i, поэтому произведение всей цепочки корректно определено. Если перемножать матрицу размера a x b на матрицу размера b x c, то это требует a · b · c скалярных умножений, а результат имеет размер a x c.

Хотя итоговая матрица не зависит от расстановки скобок, общее число скалярных умножений может сильно различаться. Требуется определить минимальное число скалярных умножений, необходимое для вычисления всего произведения.

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

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

Вторая строка содержит n + 1 целых чисел p_0, p_1, ..., p_n, задающих размеры матриц.

Это означает, что:

• A_1 имеет размер p_0 x p_1,
• A_2 имеет размер p_1 x p_2,
• ...
• A_n имеет размер p_{n-1} x p_n.

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

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

Ограничения

• 1 <= n <= 300
• 1 <= p_i <= 500
• ответ может не помещаться в 32-битный целочисленный тип

Примеры

Пример 1

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

1
7 13

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

0

Пример 2

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

2
5 10 3

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

150