Hide

Problem A
Töflur

Languages en is

Þú elskar að spila leiki með vinkonu þinni. Núna eruð þið að spila leik þar sem hver leikmaður fær $n$ reiti með tölu á. Hver leikmaður setur svo reitina niður á borð í röð að þeirra vali. Látum $a_ j$ tákna töluna á $j$-ta reitnum í röð leikmanns, fyrir $j=1,2,\ldots ,n$. Fjöldi stiga sem leikmaðurinn fær fyrir þessa röð er reiknuð með því að skoða hverjar tvær tölur sem eru hlið við hlið, taka mismun þeirra og setja þær í annað veldið, og leggja svo saman allar niðurstöðurnar, þ.e.

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

Leikmaðurinn með lægsta stigafjöldann vinnur.

Inntak

Fyrsta lína inniheldur heiltölu $n$ ($1\leq n\leq 10^6$), fjöldi reita. Næsta lína inniheldur $n$ heiltölur, tölurnar á reitunum, sem eru að minnsta kosti $1$ en ekki stærri en $10^6$.

Úttak

Skrifið út eina línu með minnsta mögulega stigafjölda ef leikmaður raðar reitunum á sem bestan máta.

Stigagjöf

Hópur

Stig

Takmarkanir

1

15

$n = 3$

2

42

$n \leq 18$

3

43

Engar frekari takmarkanir

Sample Input 1 Sample Output 1
9
1 2 3 1 1 2 2 3 3
2
Sample Input 2 Sample Output 2
7
4 8 7 25 95 97 6
5199