#include<queue>
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<memory.h>
#include <cmath>

using namespace std;

struct node
{
	int father;
	int left,right;
	int value=0;
	int count=0;
}tree[327690];

void BST(int me,int he)
{
	if (tree[me].value==tree[he].value) 
	{
	tree[he].count++;
	tree[me].left=tree[he].left;
	tree[me].right=tree[he].right;
	tree[me].father=-1;
	tree[me].count=tree[he].count;
	return;
	}
	
	if (tree[tree[he].left].count==0 and tree[me].value<tree[he].value)
	{
		tree[he].left=me;
		tree[me].count=1;
		tree[me].father=he;
		return;
	}	//向左插入
	 
	if (tree[tree[he].right].count==0 and tree[me].value>tree[he].value)
	{
		tree[he].right=me;
		tree[me].count=1;
		tree[me].father=he;
		return;
	}	//向右插入
	
	if (tree[me].value<tree[he].value)
	{
		BST(me,tree[he].left);
		return;
	}
	
	if (tree[me].value>tree[he].value)
	{
		BST(me,tree[he].right);
		return;
	}
}

int minn(int me,int mina,int he)
{
	if (tree[me].count>1) return 0;
	if (he==1) return min( mina,abs(tree[me].value-tree[he].value) );
	else return minn(me,min(mina,abs(tree[me].value-tree[he].value) ),tree[he].father);
}

void rotate(int x,int y)
{
	if (tree[y].left==x)
	{
		if (tree[y].father==0)
		{
			tree[x].father=0;
			tree[y].father=x;
		}
		else 
		{
		if (tree[tree[y].father].left==y) tree[tree[y].father].left=x;
		else tree[tree[y].father].right=x;
		tree[x].father=tree[y].father;
		}
		
		tree[y].left=tree[x].right;
		tree[tree[y].left].father=y;
		
		tree[y].father=x;
		tree[x].right=y;
	}
	
	if (tree[y].right==x)
	{
		if (tree[y].father==0)
		{
			tree[x].father=0;
			tree[y].father=x;
		}
		else 
		{
		if (tree[tree[y].father].left==y) tree[tree[y].father].left=x;
		else tree[tree[y].father].right=x;
		tree[x].father=tree[y].father;
		}
		
		tree[y].right=tree[x].left;
		tree[tree[y].right].father=y;
		
		tree[y].father=x;
		tree[x].left=y;
	}
}

void splay(int me,int to)
{
	int fa,gr;
	if (tree[me].father==to)
	{
		rotate(me,to);
		return;
	}
	
	if (tree[tree[me].father].left==me) fa=1;
	else fa=2;
	
	if (tree[tree[tree[me].father].father].left==tree[me].father) gr=1;
	else gr=2;
	
	if (fa==gr)
	{
		rotate(tree[me].father,tree[tree[me].father].father);
		rotate(me,tree[me].father);
		if (tree[me].father==0) return;
		else splay(me,to);
	}
	else
	{
		rotate(me,tree[me].father);
		rotate(me,tree[me].father);
		if (tree[me].father==0) return;
		else splay(me,to);
	}
	
}

int minne(int me)
{
	int ql,pr;
	if (tree[me].count>1) return 0;
	if (tree[me].left==0) ql=-1;
	else 
	{
		ql=tree[me].left;
		while (tree[ql].right!=0)
		{
			ql=tree[ql].right;
		}
	}
	
	if (tree[me].right==0) pr=-1;
	else 
	{
		pr=tree[me].right;
		while (tree[pr].left!=0)
		{
			pr=tree[pr].left;
		}
	}
	
	if (ql==-1) return abs(tree[pr].value-tree[me].value);
	if (pr==-1) return abs(tree[ql].value-tree[me].value);
	return min(abs(tree[pr].value-tree[me].value),abs(tree[ql].value-tree[me].value));
}

int main()
{
	long long int n;
	int s=0;
	cin>>n;
	cin>>tree[1].value;
	tree[1].count=1;
	s=tree[1].value;
	for (int i=2;i<=n;++i)
	{
		cin>>tree[i].value;
		int si=i-1;
		
		while (tree[si].father!=0)
		si--;
		//cout<<"^^^"<<i<<" "<<si<<endl;
		BST(i,si);

		if (tree[i].count==1) splay(i,si);
		
		s=s+minne(i);
	}
	
	cout<<s;
	return 0;
}