Problem C
Töflur
You really like playing games with your friend. You are currently playing a game where each player is given $n$ tiles with numbers on them. Each player then places the tiles down such that they form a sequence. Let $a_ j$ denote the number on the $j$-th tile in the sequence, for $j=1, 2, \dotsc , n$. The score of the sequence is then computed by adding up the squares of differences of adjacent tiles, that is
\[ \sum _{j = 1}^{n - 1} (a_ j - a_{j + 1})^2. \]The player with the lowest score wins.
Input
The first line of the input is an integer $n$, the number of tiles you have, where $1 \leq n \leq 10^6$. The next line consists of $n$ integers each being at least one, but not larger than $10^6$.
Output
The only line of the output should contain one integer, the lowest score you can achieve by arranging your tiles optimally.
Scoring
|
Groups |
Points |
Constraints |
|
1 |
15 |
$n = 3$ |
|
2 |
42 |
$n \leq 18$ |
|
3 |
43 |
No further constraints |
| Sample Input 1 | Sample Output 1 |
|---|---|
9 1 2 3 1 1 2 2 3 3 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 4 8 7 25 95 97 6 |
5199 |
