Một ông chủ có \(n\) cửa hàng nằm liên tiếp trên một con phố, các cửa hàng được đánh số liên tiếp từ \(1\) đến \(n\) từ đầu phố đến cuối phố. Cửa hàng \(i\) (\(1 \le i \le n\)) có giá trị là \(p_i\).

Ông chủ có bốn người con và muốn chia \(n\) cửa hàng cho các con của mình theo cách sau.

Ông chọn ba vị trí \(x,y,z\) sao cho \(1 \le x < y < z < n\), gọi \(A = \sum_{i=1}^x p_i = p_1 + \ldots + p_x\), \(B = \sum_{i=x+1}^y p_i = p_{x+1} + \ldots + p_y\), \(C = \sum_{i=y+1}^z p_i = p_{y+1} + \ldots + p_z\) và \(D = \sum_{i=z+1}^n p_i = p_{z+1} + \ldots + p_n\), khi đó các người con lần lượt nhận các phần tương ứng \(A, B, C, D\). Theo tính toán của ông, giá trị \(S = (AC + BD)^2 + (AD - BC)^2\) càng nhỏ thì các người con càng đồng thuận.

Yêu cầu: Hãy tìm cách chia để giá trị \(S\) càng nhỏ càng tốt.

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(p_1, p_2, \ldots, p_n\) (\(p_1 + p_2 + \ldots + p_n \le 50000\)).

Output

• Gồm một dòng chứa một số nguyên là giá trị \(S\) nhỏ nhất tìm được.

Scoring

• Subtask \(1\) (\(28\%\) số điểm): \(n \le 30\).
• Subtask \(2\) (\(28\%\) số điểm): \(n \le 400\).
• Subtask \(3\) (\(28\%\) số điểm): \(n \le 5000\).
• Subtask \(4\) (\(16\%\) số điểm): \(n \le 50000\).

Example

6
1 1 2 1 1 2

36