






Problem description
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 |
|
|
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 |
|
|
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 |