== include(page="template/taskheader" task_id="profit") ==
De curând, Don BJ a încheiat un contract de colaborare cu o binecunoscută companie care furnizează energie electrică. Primul lucru pe care îl are de făcut Don BJ este acela de a verifica stâlpii de înaltă tensiune. După o scurtă inspecţie, el a observat că există $N$ stâlpi aşezaţi în linie (numerotaţi de la 1 la N), fiecare având o înalţime dată {$A$}~i~. Deoarece Don BJ este o persoană cu simţ estetic, el acum doreşte să modifice înalţimile stâlpilor astfel încât, la final, acestea să formeze o secvenţă fie crescătoare, fie descrescătoare. Cu alte cuvinte, Don BJ vrea să creeze o nouă secvenţă {$B$}~1~, {$B$}~2~, .., {$B$}~n~ în care fie {$B$}~1~ ≤ {$B$}~2~ ≤ .. ≤ {$B$}~n~, fie {$B$}~1~ ≥ {$B$}~2~ ≥ .. ≥ {$B$}~n~.
Costul total de a modifica secvenţa este $|A$~1~ $– B$~1~$| + |A$~2~ $– B$~2~$| + .. + |A$~n~ $– B$~n~$|$. Deoarece Don BJ este un afacerist înnăscut el doreşte ca în final costul total de a aranja stâlpii să fie minim.
De curând, Don BJ a încheiat un contract de colaborare cu o binecunoscută companie care furnizează energie electrică. Primul lucru pe care îl are de făcut Don BJ este acela de a verifica stâlpii de înaltă tensiune. După o scurtă inspecţie, el a observat că există $N$ stâlpi aşezaţi în linie (numerotaţi de la $1$ la $N$), fiecare având o înalţime dată {$A{~i~}$}. Deoarece Don BJ este o persoană cu simţ estetic, el acum doreşte să modifice înalţimile stâlpilor astfel încât, la final, acestea să formeze o secvenţă fie crescătoare, fie descrescătoare. Cu alte cuvinte, Don BJ vrea să creeze o nouă secvenţă {$B{~1~}$}, {$B{~2~}$}, .., {$B{~n~}$} în care fie {$B{~1~}$} ≤ {$B{~2~}$} ≤ .. ≤ {$B{~n~}$}, fie {$B{~1~}$} ≥ {$B{~2~}$} ≥ .. ≥ {$B{~n~}$}.
Costul total de a transforma secvenţa este $|A{~1~} – B{~1~}|$ + $|A{~2~} – B{~2~}|$ + .. + $|A{~n~} – B{~n~}|$. Deoarece Don BJ este un afacerist înnăscut el doreşte ca în final costul total de a aranja stâlpii să fie minim.
Deoarece v-a promis un procent foarte mare din profiturile tuturor afacerilor sale, voi trebuie să calculaţi acest cost minim.
h2. Date de intrare
Pe prima linie a fişierului $profit.in$ se află $N$, numărul de stâlpi. Pe următoarele $N$ linii se află înălţimile $A$~i~ ale stâlpilor de înaltă tensiune (pe linia $i + 1$ se găseşte $A$~i~).
Pe prima linie a fişierului $profit.in$ se află $N$, numărul de stâlpi. Pe următoarele $N$ linii se află înălţimile {$A{~i~}$} ale stâlpilor de înaltă tensiune (pe linia $i+1$ se găseşte {$A{~i~}$}).
h2. Date de ieşire
Fişierul $profit.out$ trebuie să conţină un singur număr, costul minim de a aranja stâlpii.
Fişierul $profit.out$ trebuie să conţină un singur număr, costul minim pentru a transforma secvenţa din fişierul de intrare într-o secvenţă crescătoare sau descrescătoare.
h2. Restricţii
* $1$ ≤ $N$ ≤ $2000$
* Înălţimile stâlpilor de află în intervalul $[0, 10$^9^{$]$}
* Don BJ ştie cu siguranţă că rezultatul va intra pe un întreg cu $32$ biţi.
* $1 ≤ N ≤ 2000$
* Înălţimile stâlpilor sunt numere naturale din intervalul {$[0, 10^9^]$}
* Don BJ ştie cu siguranţă că rezultatul se încadrează într-un întreg reprezentat pe $32$ de biţi
h2. Exemplu
