Problem Description

Rar the Cat has been excessively using his mobile data for the past N days. On day i, he would use Di bytes of mobile data.

Now, the mobile service provider wants to charge Rar the Cat for his data usage.

If Rar the Cat subscribes to a X bytes plan, he would have to pay X cents if his usage that day does not exceed X. That is, DiX. However, if his data usage exceeds X (Di > X), he would have to pay the cost of the plan, plus the square of the difference in data used, X + (Di - X)2. The total sum Rar the Cat has to pay will be the sum of charges for each day.

However, Rar the Cat can only subscribe to a single plan for the entire duration of N days. By optimally chosing the value of X, Rar the Cat realises he can minimize the total amount of money he has to pay. He wants you to write a program to find out what is this minimum total amount of money, in cents.

Limits

Subtask 1 (7%): 1 ≤ N ≤ 2000, 0 ≤ Di ≤ 1000. In addition, Rar the Cat will use the same amount of data each day. (Di = D1 for all i > 1)

Subtask 2 (28%): 1 ≤ N ≤ 2000, 0 ≤ Di ≤ 1000

Subtask 3 (18%): 1 ≤ N ≤ 2000, 0 ≤ Di ≤ 106

Subtask 4 (47%): 1 ≤ N ≤ 200000, 0 ≤ Di ≤ 106

Subtask 5 (0%): Sample Testcases.

Input

The first line of input will contain one integer, N.

The second line of input will contain N integers, representing the array D.

Output

The output should contain of one integer, the minimum total amount of money Rar the Cat has to pay.

Sample Testcase 1

Input

10
1 2 9 5 7 6 3 4 2 2

Output

70

Explanation

By using a X = 6 data plan, we can obtain the minimum cost of 70.

Data Usage, DiFixed CostAdditional Cost
16-
26-
96(9-6)2 = 9
56-
76(7-6)2 = 1
66-
36-
46-
26-
26-

If X = 5 was chosen, the total cost would have been 71. Alternatively, if X = 7 was chosen, the total cost would have been 74.

Sample Testcase 2

Input

2
0 100

Output

199

Sample Testcase 3

Input

5
7 7 7 7 7

Output

35