Fişierul intrare/ieşire:	profit.in, profit.out	Sursă	infoarena 2.0
Autor	Din Folclor	Adăugată de	Andrei Parvu •andrei.12
Timp execuţie pe test	0.05 sec	Limită de memorie	8192 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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₁, B₂, .., B_n în care fie B₁ ≤ B₂ ≤ .. ≤ B_n, fie B₁ ≥ B₂ ≥ .. ≥ B_n.
Costul total de a transforma secvenţa este |A₁ – B₁| + |A₂ – B₂| + .. + |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.

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

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.

Restricţii

• 1 ≤ N ≤ 2000
• Înălţimile stâlpilor sunt numere naturale din intervalul [0, 10⁹]
• Don BJ ştie cu siguranţă că rezultatul se încadrează într-un întreg reprezentat pe 32 de biţi

Exemplu

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.

Cum se trimit solutii?