思路：单调博弈问题

解题过程

引入一个结论：

如果一段序列中，出现了三个相邻位置 $A$，$B$，$C$，满足 $A \le B≥C$，那么可以把这三个数替换成 $A−B+C$。原因是假设先手某一次要取 $A$（要取 $C$ 同理），显然如果要取 $A$，说明此时 $A$ 是最优决策，然后后手一定会取 $B$，因为后手选 $B$ 一定不差。同理，先手后面会取 $C$，这样取完三个数先手收益就是 $A−B+C$。

程序实现

做完以后，所有栈/队列都会变成先递减后递增的形式。对于队列，因为可以从两边取，那么每次只要取最大值：

1. 可以把所有队列元素放在一起排序，然后依次取；对于栈元素，从栈顶开始一直递减的那一段也是和队列一样的。

2. 递增的一段，显然先手一取，后手就会取下一个，导致先手亏，所以谁都不会先取。把这一部分单独处理，即从栈底开始两两配对，把亏损的代价统计，放在最后面，看谁会取到即可。

3. 最后通过简单的和差问题即可获得答案。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int lint
typedef long long lint;
typedef long double louble;
template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return b<a?a:b;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}
namespace ae86{
	const int bufl = 1<<15;
	char buf[bufl],*s=buf,*t=buf;
	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}
	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}
}
using ae86::ty;
const int _ = 1000007;
lint stk[_]={0},temp[_];
int got[_]={0},n,top=0,ltemp=0;
signed main()
{
	int who=0;
	lint sum=0,ans=0;
	n=ty();
	for(int i=1;i<=n;i++)
	{
		stk[++top]=ty(),got[top]=0;
		if(stk[top]>0)who^=1,sum+=stk[top],got[top]=1;
		while(top>=3 && got[top] && got[top-1] && got[top-2]
				&& stk[top-2]<=stk[top-1] && stk[top]<=stk[top-1])
			stk[top-2]=stk[top-2]+stk[top]-stk[top-1],got[top]=got[top-1]=0,stk[top]=stk[top-1]=0,top-=2;
	}
	int l=1,r=top;
	who=who+who-1;
	for(l=1;l<=top && got[l] && got[l+1] && stk[l]>=stk[l+1];l+=2)
		ans=ans+(stk[l]-stk[l+1])*who;
	for(r=top;r>l && got[r] && got[r-1] && stk[r]>=stk[r-1];r-=2)
		ans=ans+(stk[r]-stk[r-1])*who;
	for(int i=l;i<=r;i++)if(got[i])temp[++ltemp]=stk[i];
	sort(temp+1,temp+ltemp+1,greater<int>());
	for(int i=1;i<=ltemp;i++)ans=ans+(i&1?(1ll):(-1ll))*temp[i];
	printf("%lld %lld\n",(sum+ans)/2,(sum-ans)/2);

	return 0;
}