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, Di ≤ X. 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, Di | Fixed Cost | Additional Cost |
|---|
| 1 | 6 | - |
| 2 | 6 | - |
| 9 | 6 | (9-6)2 = 9 |
| 5 | 6 | - |
| 7 | 6 | (7-6)2 = 1 |
| 6 | 6 | - |
| 3 | 6 | - |
| 4 | 6 | - |
| 2 | 6 | - |
| 2 | 6 | - |
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