Profit

profit

== 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 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.

Poveste şi cerinţă...

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~}$}).

Fişierul de intrare $profit.in$ ...

h2. Date de ieşire

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.

În fişierul de ieşire $profit.out$ ...

h2. Restricţii

* $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
table(example). |_. profit.in |_. profit.out |

| 4
1
5
3
10
|2

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Don BJ hotărăşte să aducă stâlpul $2$ la înălţimea $4$ şi stâlpul $3$ la înălţimea $4$. Astfel costul total este $|5 - 4| + |3 - 4| = 2$. Acesta este şi costul minim.

...

== include(page="template/taskfooter" task_id="profit") ==

4827