Tý có một nhà kho có \(N\) đồ vật cần được sắp xếp lên kệ. Mỗi đồ vật có kích thước \(a_i\). Các đồ vật được xếp thành từng nhóm liên tiếp nhau.

Khi xếp một nhóm từ đồ vật \(j+1\) đến đồ vật \(i\) vào một kệ, chi phí được tính bằng \((i - j - 1 + \sum_{k=j+1}^{i} a_k)^2\). Nói cách khác, chi phí bằng bình phương của (số khe hở giữa các đồ vật + tổng kích thước).

Hãy chia dãy đồ vật thành các nhóm liên tiếp sao cho tổng chi phí là nhỏ nhất.

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^3\)).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Ví dụ

Input:

5
2 3 1 4 2

Output:

75

Ràng buộc

• Subtask 1 (30%): \(N \le 2000\).
• Subtask 2 (30%): \(N \le 10^4\).
• Subtask 3 (40%): \(N \le 10^5\).