Kangaroo Party

Interview

Time limit1sMemory limit512 MB

Summary

Given n distinct house positions, pick two of them as party houses so the sum of squared distances from every house to its nearest party house is minimized.

Level: Medium5 of 10
Topics: Sorting, Brute force, Math, Implementation
Solved: No attempts yet

Problem

A group of kangaroos lives in houses on the number line. They all want to watch the Kangaroo Bowl!

Because not all of the kangaroos fit in a single house, they pick two kangaroos to each host a party at their house. Every other kangaroo goes to the house closest to it, choosing arbitrarily when the two houses are equally far away.

A kangaroo spends $(a - b)^2$ units of energy to travel from location $a$ to location $b$ . Given that the locations of the two party houses are chosen optimally, compute the minimum total units of energy spent by all the kangaroos.

Input

The first line contains a single integer $n$ ( $2 \le n \le 50$ ), the number of kangaroos.

Each of the next $n$ lines contains a single integer $x$ ( $-1,000 \le x \le 1,000$ ), the location on the number line of one kangaroo's house. Each location is distinct.

Output

Print on a single line the minimum total units of energy spent by all the kangaroos when the locations of the two party houses are chosen optimally.

Examples1

Example 1
Input
```
5
0
3
-3
10
11
```
Expected output
```
19
```