记录编号	176802	评测结果	AAAAAAAAAA
题目名称	[HNOI 2002]营业额统计	最终得分	100
用户昵称	lenibomb	是否通过	通过
代码语言	C++	运行时间	0.186 s
提交时间	2015-08-09 21:15:20	内存使用	19.37 MiB

#define M 1000020
#define MIN(a,b) (a)<(b)?(a):(b)
#include<cstdio>
#define LL long long
using namespace std;
int son[M][2],pre[M];
LL val[M],ans;
int n,m,root;
LL abs(LL a,LL b){
	if(a-b>0) return a-b;
	else return b-a;
}
void Turn(int x,int op){
	int y=pre[x];
	son[y][!op]=son[x][op];
	pre[son[x][op]]=y;
	if(pre[y]){
		son[pre[y]][son[pre[y]][1]==y]=x;
	}
	pre[x]=pre[y];
	son[x][op]=y;
	pre[y]=x;
	return ;
}
int UP(int rt,int x)
{
	while(pre[x]!=rt){
		int y = pre[x];
		int op = son[y][1]==x;
	/*	puts("AC");
		printf("pre[x] = %d\n",pre[x]);printf("pre[y] = %d\n", pre[y]);*/
		if(pre[y]==rt){
			Turn(x,!op);
		}
		else if(son[pre[y]][op]==y){
			Turn(y,!op);
			Turn(x,!op);
		}
		else{
			Turn(x,!op);
			Turn(x,op);
		}
	}
	if(!rt)
		root=x;
}
int Lfind(int rt){
	while(son[rt][1]!=0){
		rt=son[rt][1];
	}
	if(!rt)
		return M<<10;
	else
		return val[rt];		
}
int Rfind(int rt){
	while(son[rt][0]!=0){
		rt=son[rt][0];
	}
	if(!rt)
		return M<<10;
	else
		return val[rt];
}
void insert(int rt,int x){
	while(son[rt][val[rt]<val[x]])
	{
	/*	if(val[rt]==val[x])
		{	
			UP(0,rt);return ;
		}*/
		rt=son[rt][val[rt]<val[x]];
	}
	son[rt][val[x]>val[rt]] = x;
	pre[x]=rt;
	UP(0,x);
//	puts("ss");
	LL a1=Lfind(son[x][0]);
	//printf("LEFT = %lld  ",a1);
	LL b1=Rfind(son[x][1]);
//	printf("RTGF = %lld  \n",b1);
	ans+=MIN( abs(a1,val[x]), abs(b1,val[x]) );
}
int main()
{
	freopen("turnover.in","r",stdin);
	freopen("turnover.out","w",stdout);
	scanf("%d",&n);
	LL x;
	scanf("%lld",&val[1]);
	root=1;
	ans+=val[1];
	for(int i=2;i<=n;i++) {
		scanf("%lld", &val[i]);
		insert( root, i);
	//	printf("===%lld\n",ans);
	}
	printf("%lld",ans);
}