Bạn An có một dãy số gồm ~N~ phần tử nguyên dương ~a_1~, ~a_2~, ..., ~a_N~ . An muốn tính tổng các số trong dãy. Vấn đề ở đây là chiếc máy tính của An khá chậm nên cậu ta muốn tìm cách tính tổng các số nguyên dương trong dãy sao cho thời gian máy tính hoạt động nhỏ nhất có thể. Cụ thể:

• Chỉ có thể cộng hai phần tử liên tiếp;

• Sau khi cộng hai phần tử liên tiếp, hai phần tử sẽ bị xoá khỏi dãy và phần tử mới bằng tổng hai phần tử sẽ được thêm vào vị trí xoá, vị trí tương đối giữa các phần tử trong dãy mới giữ nguyên;

• Thời gian để tính tổng hai số nguyên dương ~x~ và ~y~ là ~(x + y)^2~.

Yêu cầu: Bạn hãy đưa ra thời gian ít nhất để máy tính có thể tính được tổng cả dãy số mà An muốn tính.

Input

Dòng đầu tiên gồm một số nguyên dương ~N~ (~N \le 3000~) — độ dài dãy số.

Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, \cdots, a_N~ (~a_i \le 10^4~) — dãy ~a~.

Output

In ra kết quả bài toán.

Scoring

Sample Input 1

3
3 4 5

Sample Output 1

193

Notes

• Tính ~3 + 4 = 7~ với thời gian ~(3 + 4)^2 = 49~;

• Tính ~7 + 5 = 12~ với thời gian ~(7 + 5)^2 = 144~;

• Như vậy tổng thời gian máy tính phải thực hiện là ~49 + 144 = 193~.