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, \ldots , n$. The score of the sequence is then computed by adding up the squares of the differences of adjecent tiles, that is

\[ \sum _{j = 1}^{n - 1} (a_ j - a_{j + 1})^2. \]

The player with the lowest score wins.


The first line of the input is an integer $1 \leq n \leq 10^6$, the number of tiles you have. The next line consists of $n$ integers each being at least one, but not larger than $10^6$, the numbers on the tiles.


The only line of the output should contain one integer, the lowest score you can achieve by arranging your tiles optimally.

Sample Input 1 Sample Output 1
1 2 3 1 1 2 2 3 3
Sample Input 2 Sample Output 2
4 8 7 25 95 97 6
CPU Time limit 2 seconds
Memory limit 1024 MB
Difficulty 2.4easy
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in