#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=600009;

int n;

long long ans=0;

int fa[maxn]={0},ch[maxn][2]={0},ky[maxn]={0},dis[maxn]={0},siz[maxn]={0};

int Getf(int x){

	while(fa[x])x=fa[x];

	return x;

}

int Mer(int x,int y){

	if((x==0)||(y==0))return x^y;

	if(ky[x]<ky[y])swap(x,y);

	ch[x][1]=Mer(ch[x][1],y);

	fa[ch[x][1]]=1;

	siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;

	if(dis[ch[x][1]]>dis[ch[x][0]])swap(ch[x][0],ch[x][1]);

	dis[x]=dis[ch[x][1]]+1;

	return x;

}

struct Sec{

	int l,r,root;

	Sec(){}

	Sec(int ll,int rr,int x){

		l=ll;r=rr;root=x;

	}

	void poppoint(){

		int tm=(r-l+2)/2;

		while(siz[root]>tm){

			fa[ch[root][0]]=0;

			fa[ch[root][1]]=0;

			root=Mer(ch[root][0],ch[root][1]);

		}

	}

}Sta[maxn];

int top=0;

int ab(int x){

	if(x<0)return -x;

	else return x;

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;++i){

		scanf("%d",&ky[i]);

		siz[i]=1;

	}

	for(int i=1;i<=n;++i){

		Sta[++top]=Sec(i,i,i);

		while(top>=2){

			if(ky[Sta[top].root]>=ky[Sta[top-1].root])break;

			Sta[top-1].root=Mer(Sta[top-1].root,Sta[top].root);

			--top;

			Sta[top].r=i;

			Sta[top].poppoint();

		}

	}

	for(int j=1;j<=top;++j){

//		cout<<Sta[j].l<<' '<<Sta[j].r<<' '<<ky[Sta[j].root]<<endl;

		for(int i=Sta[j].l;i<=Sta[j].r;++i){

			ans+=ab(ky[Sta[j].root]-ky[i]);

		}

	}

	cout<<ans<<endl;

	return 0;

}