记录编号	268823	评测结果	AAAAAAAAAA
题目名称	[HNOI 2002]营业额统计	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.057 s
提交时间	2016-06-12 19:53:08	内存使用	1.27 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn=50010;
int n,a[maxn],p[maxn],rp[maxn],l[maxn],r[maxn];
bool cmp(int x,int y){
	return a[x]<a[y];
}
int main(){
#ifndef ONLINE_JUDGE
	freopen("turnover.in","r",stdin);
	freopen("turnover.out","w",stdout);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		p[i]=i;
	}
	int ans=a[1];
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;i++){
		l[i]=i-1;r[i]=i+1;
		rp[p[i]]=i;
	}
	l[1]=n;r[n]=1;
	for(int i=n;i>=2;i--){
		ans+=min(abs(a[i]-a[p[l[rp[i]]]]),abs(a[p[r[rp[i]]]]-a[i]));
		r[l[rp[i]]]=r[rp[i]];
		l[r[rp[i]]]=l[rp[i]];
	}
	printf("%d\n",ans);
	return 0;	
}