Bạn được cho n hòn đá, mỗi hòn đá có cân nặng là a[i].

Bạn phải chất các hòn đá thành từng đống liên tiếp nhau và giữ đúng thứ tự các đống so với dãy hòn đá ban đầu.

Mỗi hòn đá ban đầu được coi là một đống, khi bạn chất hai đống liên tiếp i và i+1 thì sẽ tốn chi phí bằng tổng cân nặng của hai đống đá đó và đống đá mới vừa chất sẽ có cân nặng là a[i] + a[i + 1].

Nhiệm vụ của bạn là chất tất cả các hòn đá này thành một đống đá với chi phí nhỏ nhất có thể.

Đầu vào

• Dòng đầu tiên gồm số nguyên dương n ~(1 \le n \le 100)~, số lượng hòn đá ban đầu.
• Dòng tiếp theo gồm n nguyên dương ~a_i~ ~(1 \le a[i] \le 10^9)~, cách nhau bởi dấu cách, cân nặng của từng hòn đá.

Đầu ra

In ra một số nguyên duy nhất là đáp án của bài toán

Sample Input

4
6 8 1 9

Sample Output

48

Giải thích:

(6, 8, 1, 9) -> (6, 9, 9) -> (15, 9) -> (24)
Chi phí 9 + 15 + 24 = 48