#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

using namespace std;

const int inf=1E9;

inline const int max(const int &a,const int &b){return a>b?a:b;}

inline const int min(const int &a,const int &b){return a<b?a:b;}

struct node{

	node();

	node *fa,*ch[2];

	int d;

	short pl(){return this==fa->ch[1];}

}*null;

node::node(){ch[0]=ch[1]=fa=null;}

namespace Splay{

	node *ROOT;

	void build(){

		null=new node;

		*null=node();

		ROOT=null;

	}

	void rotate(node *k){

		node *r=k->fa; if (k==null||r==null) return;

		int x=k->pl()^1;

		r->ch[x^1]=k->ch[x];

		r->ch[x^1]->fa=r;

		if (r->fa==null) ROOT=k;

		else r->fa->ch[r->pl()]=k;

		k->fa=r->fa; r->fa=k;

		k->ch[x]=r;

	}

	void splay(node *r,node *tar=null){

		for (;r->fa!=tar;rotate(r))

		 if (r->fa->fa!=tar)rotate(r->pl()==r->fa->pl()?r->fa:r);

	}

	void insert(int x){

		if (ROOT==null){

			ROOT=new node;

			ROOT->d=x;

			return;

		}node *r=ROOT;

		while (1){

			int c;

			if (x<r->d) c=0;

			else c=1;

			if (r->ch[c]==null){

				r->ch[c]=new node;

				r->ch[c]->d=x;

				r->ch[c]->fa=r;

				splay(r->ch[c]);

				return;

			}else r=r->ch[c];

		}

	}

	int leftmax(){

		node *r=ROOT->ch[0];

		while (r->ch[1]!=null) r=r->ch[1];

		return r->d;

	}

	int rightmin(){

		node *r=ROOT->ch[1];

		while (r->ch[0]!=null) r=r->ch[0];

		return r->d;

	}

	int que(){

		int x=inf;

		if (ROOT->ch[0]!=null) x=ROOT->d-leftmax();

		if (ROOT->ch[1]!=null) x=min(x,rightmin()-ROOT->d);

		return x;

	}

}

int getint(){char c;int fh=1;while (!isdigit(c=getchar()))if(c=='-')fh=-1;int a=c-'0';while (isdigit(c=getchar()))a=a*10+c-'0';return a*fh;}

int main(){

	int n=getint();

	Splay::build();

	int x=getint();

	long long ans=x;

	Splay::insert(x);

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

		x=getint();

		Splay::insert(x);

		ans+=Splay::que();

	}printf("%lld\n",ans);

	return 0;

}