记录编号	423617	评测结果	AAAAAAAAAA
题目名称	[HNOI 2002]营业额统计	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.148 s
提交时间	2017-07-12 10:22:10	内存使用	1.81 MiB

#include<cstdio>
#include<algorithm>
#include<ctime>
using namespace std;
const int N=1e5+10;
int n,l[N],r[N],k[N],ran[N],root,top;
int l_rot(int x){
	int y=r[x];
	r[x]=l[y];l[y]=x;
	return y;
}
int r_rot(int x){
	int y=l[x];
	l[x]=r[y];r[y]=x;
	return y;
}
int insert(int x,int key){
	if (!x){
		k[++top]=key;
		l[top]=r[top]=0;
		ran[top]=rand();
		return top;
	}
	if (k[x]<key) r[x]=insert(r[x],key);
		else l[x]=insert(l[x],key);
	if (ran[r[x]]>ran[x]) x=l_rot(x);
	if (ran[l[x]]>ran[x]) x=r_rot(x);
	return x;
}
int pre(int x,int key){
	if (!x) return -1e9;
	return key>=k[x]?max(k[x],pre(r[x],key)):pre(l[x],key);
}
int suc(int x,int key){
	if (!x) return 1e9;
	return key<=k[x]?min(k[x],suc(l[x],key)):suc(r[x],key);
}
int main()
{
	freopen("turnover.in","r",stdin);
	freopen("turnover.out","w",stdout);
	srand(time(0));
	scanf("%d",&n);
	long long ans=0;
	for (int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		if (i==1) ans+=x;
			else ans+=min(x-pre(root,x),suc(root,x)-x);
		root=insert(root,x);
	}
	printf("%lld\n",ans);
	return 0;
}