Набридли довгі умови задач?

Вам дано масив $a$ цілих чисел $a_1,a_2,\dots ,a_n$.

Ви можете виконати наступну операцію будь-яку кількість разів (можливо, нуль):

• вибрати індекси $i,j$ $(1\le i,j\le n)$ та обміняти місцями $a_i$ та $a_j$.

Нехай $f(a)$ дорівнює:

Іншими словами, $f(a)$ дорівнює сумі квадратів різниць сусідніх елементів масиву $a$.

Знайдіть мінімально можливе значення $f(a)$ після виконання будь-якої кількості операцій (можливо, нуль).

Вхідні дані

Перший рядок містить одне ціле число $n$ $(1\le n\le 5\cdot 10^5)$ — довжина масиву $a$.

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ $(0\le a_i\le 10^9)$ — елементи масиву $a$.

Вихідні дані

Виведіть одне ціле число — мінімально можливе значення $f(a)$.

Приклади

Примітка

Для першого прикладу, після кількох операцій можливі значення $f(a)$ такі:

• $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$.

Оцінювання

1. ($3$ бали): $a_1=a_2=\cdots =a_n$;

2. ($8$ балів): $n\le 9$;

3. ($15$ балів): $n\le 500$;

4. ($16$ балів): В масиві $a$ не більше $10$ різних значень;

5. ($28$ балів): $n\le 10000$;

6. ($30$ балів): без додаткових обмежень.