#include <cstdio>#include <vector>#include <algorithm>using namespace std;struct node{    int Left, Right, Height;    vector<int> Lower;};typedef long long int64;int N, M;int Seq[5000];node Nodes[5000];int64 Result;int main(){    int I, J;    scanf("%d", &N);    for (I = 0; I < N; I++) scanf("%d", Seq + I);    M = 0;    for (I = 0; I < N; I++)        if (M == 0 || Seq[I] > Nodes[M - 1].Height)        {            Nodes[M].Left = Nodes[M].Right = I;            Nodes[M++].Height = Seq[I];        }        else        {            Nodes[M - 1].Right++;            if (Seq[I] < Nodes[M - 1].Height)            {                Nodes[M - 1].Lower.push_back(Seq[I]);                push_heap(Nodes[M - 1].Lower.begin(), Nodes[M - 1].Lower.end());            }            while (Nodes[M - 1].Lower.size() * 2 >= Nodes[M - 1].Right - Nodes[M - 1].Left + 1)            {                J = Nodes[M - 1].Lower[0];                if (M > 1 && Nodes[M - 2].Height > J) J = Nodes[M - 2].Height;                while (!Nodes[M - 1].Lower.empty() && Nodes[M - 1].Lower[0] >= J)                {                    pop_heap(Nodes[M - 1].Lower.begin(), Nodes[M - 1].Lower.end());                    Nodes[M - 1].Lower.pop_back();                }                Nodes[M - 1].Height = J;                if (M > 1 && Nodes[M - 2].Height == J)                {                    M--;                    if (Nodes[M - 1].Lower.size() < Nodes[M].Lower.size()) Nodes[M - 1].Lower.swap(Nodes[M].Lower);                    Nodes[M - 1].Lower.reserve(Nodes[M - 1].Lower.size() + Nodes[M].Lower.size());                    while (!Nodes[M].Lower.empty())                    {                        Nodes[M - 1].Lower.push_back(Nodes[M].Lower.back());                        push_heap(Nodes[M - 1].Lower.begin(), Nodes[M - 1].Lower.end());                        Nodes[M].Lower.pop_back();                    }                    Nodes[M].Lower.clear();                    Nodes[M - 1].Right = Nodes[M].Right;                }            }        }    Result = 0;    for (I = 0; I < M; I++) for (J = Nodes[I].Left; J <= Nodes[I].Right; J++)        if (Seq[J] < Nodes[I].Height) Result += Nodes[I].Height - Seq[J];        else Result += Seq[J] - Nodes[I].Height;    printf("%I64d\n", Result);    return 0;}