Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là chia mảng thành \(n\) mảng con, mỗi mảng con có duy nhất một phần tử.

Ở mỗi lần thực hiện, bạn có thể chọn một mảng con bất kì và chia nó thành hai mảng con. Chi phí cho mỗi lần thực hiện là tổng các giá trị trong mảng con đã chọn.

Tổng chi phí tối thiểu là bao nhiêu nếu bạn thực hiện một cách tối ưu?

Input

Dòng đầu vào đầu tiên có một số nguyên \(n\): kích thước mảng. Các phần tử của mảng được đánh số \(1, 2, \ldots, n\).

Dòng thứ hai gồm \(n\) số nguyên \(x_1, x_2, \ldots, x_n\) : các giá trị của mảng

Output

In ra một số nguyên: tổng chi phí tối thiểu.

Constraints

• \(1 \leq n \leq 5000\)
• \(1 \leq x_i \leq 10 ^ 9\)

Example

Sample input

5
2 7 3 2 5

Sample output

43