Bored of Long Statements?

You are given an array $a$ of integers $a_1,a_2,\dots ,a_n$.

You can perform the following operation any number of times (possibly zero):

• choose indexes $i,j$ $(1\le i,j\le n)$ and swap $a_i$ and $a_j$.

Let $f(a)$ be:

In other words, $f(a)$ is equal to the sum of squared differences of adjacent elements of $a$.

Find the minimum possible value of $f(a)$ after performing any number of operations (possibly zero).

Input

The first line contains a single integer $n$ $(1\le n\le 5\cdot 10^5)$ — the length of $a$.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ $(0\le a_i\le 10^9)$ — elements of $a$.

Output

Output a single integer — minimum possible $f(a)$.

Examples

Note

For the first example, after several operations, the possible values of $f(a)$ are:

• $f([1,5,10])=(5-1{)}^2+(10-5{)}^2=41$;

• $f([1,10,5])=(10-1{)}^2+(5-10{)}^2=106$;

• $f([5,1,10])=(1-5{)}^2+(10-1{)}^2=97$;

• $f([5,10,1])=(10-5{)}^2+(1-10{)}^2=106$;

• $f([10,1,5])=(1-10{)}^2+(1-5{)}^2=97$;

• $f([10,5,1])=(5-10{)}^2+(1-5{)}^2=41$.

Scoring

1. ($3$ points): $a_1=a_2=\cdots =a_n$;

2. ($8$ points): $n\le 9$;

3. ($15$ points): $n\le 500$;

4. ($16$ points): there are at most ten different $a_i$ in the array;

5. ($28$ points): $n\le 10000$;

6. ($30$ points): no additional restrictions.