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