Рабочий должен склеить в одну все кучки камней, лежащие в ряд. Изначально имеется n кучек, в i-й кучке находится a_i камней.

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

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

Требуется определить минимальную возможную суммарную стоимость всех склеек.

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

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

Во второй строке заданы n целых чисел a_i, где a_i — количество камней в i-й кучке.

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

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

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

Ограничения

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

Примеры

Пример 1

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

1
1

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

0

Пример 2

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

2
1 10000

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

10001