记录编号	172991	评测结果	AAAAAAAAAA
题目名称	[HNOI 2002]营业额统计	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.547 s
提交时间	2015-07-27 18:04:14	内存使用	0.31 MiB

#include <cstdio>
#define ABS(a) ((a)>(0)?(a):-(a))
#define MIN(a,b) (a>b?(b):(a))

using namespace std;

int n;bool flag;

struct at{
	int w;
	at * l,*r;
}*root,*null;

void rt(at * &now)
{
	at * temp=now->l;
	now->l=temp->r;
	temp->r=now;
	now=temp;
}

void lt(at * &now)
{
	at * temp=now->r;
	now->r=temp->l;
	temp->l=now;
	now=temp;
}

int find1(at * now)
{
	if(now->r==null)
	{
		return now->w;
	}
	return find1(now->r);
}

int find2(at * now)
{
	if(now->l==null)
	{
		return now->w;
	}
	return find2(now->l);
}

void insert(at * &now,int w)
{
	if(now==null)
	{
		now=new at();
		now->w=w;
		now->l=null;
		now->r=null;
		return;
	}
	if(w<now->w)
	{
		insert(now->l,w);
		rt(now);
		return;
	}
	if(w>now->w)
	{
		insert(now->r,w);
		lt(now);
		return;
	}
	flag=1;
	return;
}

int main()
{
	freopen("turnover.in","r",stdin);
	freopen("turnover.out","w",stdout);
	int ans=0;
	null=new at();
	null->w=100000000;
	null->l=null;
	null->r=null;
	root=null;
    scanf("%d",&n);
	
    for(int i=1;i<=n;i++)
    {
		int x;
		if(scanf("%d",&x)==EOF)
			x=0;
		flag=0;
		insert(root,x);
		if(flag)
			continue;
		if(i==1)
		{	
			ans+=x;
			continue;
		}
		int ans1=ABS(x-find1(root->l));
		int ans2=ABS(x-find2(root->r));
		ans+=MIN(ans1,ans2);
    }
    printf("%d",ans);
    return 0;
}