记录编号	102964	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]积木大赛	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.023 s
提交时间	2014-05-23 10:11:09	内存使用	0.60 MiB

#include <cstdio>

#define  queue_size  100010

using namespace std ;

int ans = 0 ;
int n , h ;

struct monotone_queue{
	int line[queue_size] ;
	int head ;
	int tail ;
	void push(int x)
	{
		int Ma ;
		if (x < line[ tail ])
		{
			Ma = line [tail] ;
			while ( head <= tail && x < line[ tail ] ) tail -- ;
			ans += (Ma - x) ;
		}
		line[ ++ tail ] = x ;
	}
	monotone_queue()
	{
		line[0] = 0 ;
		head = 1 ;
		tail = 0 ;
	}
}q ;

int main()
{
	freopen("BlockNOIP2013.in", "r",stdin);
	freopen("BlockNOIP2013.out","w",stdout);
	q.push(0);
	scanf("%d",&n) ;
	for (int i = 1 ; i <= n ; i ++ )
	{
		scanf("%d",&h) ;
		q.push(h) ;
	}
	q.push(0);
	printf("%d\n",ans);
	return 0 ;
}