По кругу расположены n кучек камней. В i-й кучке находится a_i камней. Первая и последняя кучки также считаются соседними.

За один ход можно склеить две соседние кучки в одну. Стоимость такого хода равна общему числу камней в этих двух кучках. После склейки вместо них появляется одна новая кучка, содержащая сумму камней из обеих.

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

Удобно рассматривать кольцо как разрезанное в некоторой точке. Для этого можно продублировать последовательность, получив массив длины 2n, и для каждого возможного начала взять отрезок длины n, соответствующий одному способу развернуть кольцо в линию. Среди всех таких разворотов требуется найти минимальную стоимость полной склейки.

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

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

Вторая строка содержит n целых чисел a_i — размеры кучек в порядке обхода по кругу.

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

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

Ограничения

• 1 <= n <= 300
• 1 <= a_i <= 10^4

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

Примеры

Пример 1

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

1
1

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

0

Пример 2

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

4
1 10000 1 10000

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

40004