# H 贪心思想+前缀和预处理

【看了官方题解后补题写出】

思路 不使用魔法容易分析，使用魔法时， 假设对 ar[i] ar[i+1] 使用魔法，即直接消灭怪物(ar[i]=0,ar[i+1]=0) 那么，需要的花费即为 处理前 i-1 个怪物与 后 i+2个 的总和 (i,i+1 已经处理完毕)

预处理 因此，先按照顺序处理 pre[i] 含义为 从 0 到 i 需要的花费 再按照逆序，处理bac[i] 含义为 从 n-1 到 i+2 的费用 都是左闭右闭的区间

贪心 先考虑 i=0 i=n-2 即 在首尾位置释放魔法的情况 再考虑普通情况

using namespace std;
#define For(n) for(int i=0;i<n;i++)
#define int long long
#define L 1000005
int pre[L],bac[L],ar[L],br[L];
signed main()
{
    int n;cin>>n;
    for (int i=0;i<n;i++)
    {
    	cin>>ar[i];br[i]=ar[i];
	}
	if(n<3)//注意，此时数量较少 1/2 可以利用魔法直接完成
	{
		cout<<0<<endl;return 0;
	}
	int d=ar[0];
	
	for (int i=0;i<n-2;i++)//预处理pre
	{
		d=max(0ll,ar[i]);//这里使用 0ll  是为了类型匹配
		if (i)pre[i]=pre[i-1]+d;
		else pre[i]=d;
		ar[i]=0;
		ar[i+1]-=d;ar[i+2]-=d;
	}
	for (int i=n-1;i-2>=0;i--)//预处理bac
	{
		d=max(0ll,br[i]);
		if (i!=n-1)		bac[i]=bac[i+1]+d;
		else {
			bac[i]=d;
		}
		br[i]=0;br[i-1]-=d;br[i-2]-=d;
	}
	
    //贪心的处理
	int ans=bac[2];
	ans = min(ans, pre[n-3]);
	//考虑 首尾的情况
	for (int i=1;i<n-2;i++)
	{
		ans=min(ans,pre[i-1]+bac[i+2]);//获取最小的费用
	}
	cout<<ans<<endl;
	
	return 0;
}