Problem description

Back
Show PDF
Sopelkowo
(B)
Limit pamięci: 64 MB
Limit czasu: 1.00 s

Sopelkowo, Lodowa Kraina.

Arktos, kręcąc się i wirując w swojej lodowej komnacie, myśląc o swoich nowych, lśniących łyżwach, wpadł na kolejny genialny pomysł:

– Jakubie, zrób mi lodowisko! Chcę mieć arenę lodową przed pałacem, na której będę mógł trenować łyżwiarstwo figurowe i zadziwiać moich poddanych piruetami. $\\$

Jakub, wierny i oddany sługa Arktosa, zna swojego króla jak nikt inny.

– Co za bałwan… – mruczy pod nosem. – Co on może wiedzieć o łyżwiarstwie? I czy on ma w ogóle nogi, na które nałoży te swoje nowe łyżwy?

Poprawił monokl i spojrzał na stare zdjęcie z dzieciństwa, na którym, jeszcze jako młody pingwinek, wykonuje perfekcyjnego axla. Łezka zakręciła mu się w oku i spadła na posadzkę jako maleńki sopelek. Choć uważał pomysł króla za absurdalny, nie miał zamiaru odmówić. Jakub wiedział, że sprzeciwianie się Arktosowi mogłoby zakończyć się w najlepszym wypadku na lodowym wygnaniu.

Problem był jednak poważny – teren przed pałacem Arktosa, zwanym Mroźnogrodem, był pełen gór i pagórków. Aby stworzyć idealnie płaskie lodowisko, Jakub musi wyrównać wysokości wszystkich górek. Każda zmiana wysokości kosztuje, a Jakub wie, że król Arktos nie przepada za niepotrzebnymi wydatkami (w końcu wydaje wszystko na nowe gadżety do lodowego pałacu).

Dokładniej, wyrównując górę o wysokości h do poziomu X, Jakub zapłaci (X−h)2.

$\\$

Teraz Jakub zwraca się do Ciebie z prośbą o pomoc. Twoim zadaniem jest obliczyć minimalny koszt wyrównania wszystkich górek tak, aby powstała idealnie płaska tafla lodu.

Wejście

W pierwszym wierszu wejścia znajduje się liczba N (1 ≤ N ≤ 106), która oznacza liczbę górek przed pałacem Arktosa.

W drugiej linii wejścia znajduje się ciąg liczb całkowitych h1, h2, …, hN (0 ≤ hi ≤ 106) - ich wysokości.

Wyjście

W jedynym wierszu wyjścia powinny jedna liczba, określająca minimalny koszt wyrównania gór. Wysokość do której wyrówane zostaną góry jest liczbą całkowitą.

Ograniczenia

1 ≤ N ≤ 106,

0 ≤ hi ≤ 106.

Przykład

Wejście Wyjście Wyjaśnienie 
5
1 1 1 1 2

1

Jakub wyrównuje góry do poziomu 1, płaci za to (1−1)2 + (1−1)2 + (1−1)2 + (1−1)2 + (1−2)2 = 1
Wejście Wyjście Wyjaśnienie 
6
0 2 3 1 4 6

24

Koszt wyrównania gór do poziomu 3 to (3−0)2 + (3−2)2 + (3−3)2 + (3−1)2 + (3−4)2 + (3−6)2 = 24