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ể. Biết rằng thời gian để tính tổng hai số nguyên dương \(x\) và \(y\) là \((x+y)^2\).

\(\textbf{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 số nguyên dương \(N\) \((N \le 3000)\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((a_i \le 10^4)\).

Output

• In ra một số duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(N \le 300\).
• Subtask \(2\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

3
3 4 5

193