#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

Rar the Cat has been excessively using his mobile data for the past *N* days. On day *i*, he would use *D _{i}* 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, *D _{i}* ≤

*X*. However, if his data usage exceeds

*X*(

*D*>

_{i}*X*), he would have to pay the cost of the plan, plus the square of the difference in data used,

*X*+ (

*D*-

_{i}*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 ≤ D_{i} ≤ 1000. In addition, Rar the Cat will use the same amount of data each day. (D_{i} = D_{1} for all *i* > 1)

Subtask 2 (28%): 1 ≤ N ≤ 2000, 0 ≤ D_{i} ≤ 1000

Subtask 3 (18%): 1 ≤ N ≤ 2000, 0 ≤ D_{i} ≤ 10^{6}

Subtask 4 (47%): 1 ≤ N ≤ 200000, 0 ≤ D_{i} ≤ 10^{6}

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, D_{i} | 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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 7 | 9 | 1s | 256MB | Minimum |

2 | 28 | 29 | 1s | 256MB | Minimum |

3 | 18 | 59 | 1s | 256MB | Minimum |

4 | 47 | 104 | 1s | 256MB | Minimum |

5 | 0 | 3 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o dataplan -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512