Ghép ngọc

Có \(N\) viên ngọc xếp thành một hàng ngang. Ban đầu, viên ngọc thứ \(i\), đếm từ trái sang, có khối lượng \(a_i\).

Yuki, một nhà khảo cổ học nổi tiếng, muốn tái tạo một viên ngọc quý hiếm bằng cách ghép các viên ngọc này lại thành một viên duy nhất. Để làm được điều đó, cô sẽ thực hiện các thao tác lặp đi lặp lại như sau:

• Yuki chọn hai viên ngọc kề nhau và ghép chúng lại. Viên ngọc mới sẽ có khối lượng là \(x + y\), trong đó \(x\) và \(y\) là khối lượng của hai viên ngọc được chọn trước khi ghép. Chi phí phát sinh từ việc ghép này là \((x + y)^2\).
• Khối lượng của viên ngọc mới sẽ thay thế hai viên cũ trong hàng, và các vị trí tương đối giữa các viên ngọc không thay đổi.

Yuki luôn cố gắng tối ưu hóa để tổng chi phí phát sinh nhỏ nhất có thể. Bạn hãy giúp cô ấy thực hiện điều này.

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((2 \leq N \leq 400)\), là số lượng viên ngọc.
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) \((1 \leq a_i \leq 10^5)\), là khối lượng ban đầu của các viên ngọc.

Output

• Ghi ra một số nguyên duy nhất là tổng chi phí phát sinh nhỏ nhất khi ghép các viên ngọc thành một viên duy nhất.

Example

5
3 2 5 7 7

897