考虑到先手和后手都使用最优策略，所以可以像对抗搜索一样，设 (val) 为先手收益减去后手收益的值。那么先手想让 (val) 尽可能大，后手想让 (val) 尽可能小。
继续分析题目性质，发现取石子的过程可以转化为两端分别有一个栈，可以从栈顶取石子，中间有若干个双端队列，可以从其两端取石子。
如果取一个位置后，接下来的位置比刚才取的那个位置权值小，也就是从选择方向开始权值是递减的，每次决策肯定都是取当前局面权值最大的位置。如果不保证递减，就有可能取完一个位置后，使得一个权值更大的位置可以取，这时按最大值决策就有可能不是最优。
对于 (a_{i-1},a_i,a_{i+1})，若其满足 (a_i geqslant a_{i-1},a_i geqslant a_{i+1})，当一次决策选 (a_{i-1}) 最优时，先手选 (a_{i-1})，其后手一定会接着选 (a_i)，然后先手会接着选 (a_{i+1})。选 (a_{i-1}) 时，当前局面一定没有比 (a_{i-1}) 更好的选择，而 (a_i) 比 (a_{i-1}) 更优，所以后手一定选 (a_i)，因为之前 (a_{i-1}) 是最优的选择，所以先手会接着选 (a_{i+1})。因此把 (a_{i-1},a_i,a_{i+1}) 对 (val) 的贡献看作整体，将其合并为一个权值为 (a_{i-1}+a_{i+1}-a_i) 的石子。
合并完后所有的权值情况只存在递增，递减和下凹的情况了，这三个情况对于双端队列都是可以单调的从大到小选，对于从栈顶方向开始递减的栈的部分位置，也是可以单调的从大到小选，这些位置就可以直接排序后先后手一个一个选了。
而对于从栈顶方向开始递增的栈的部分位置，一定是最后才开始选的，因为这些决策一定是劣于其他决策，提前处理出其选择的结果，最后根据先后手的情况分配即可。
合并删除操作可以用链表来实现。
(code:)
#include<bits/stdc++.h>
#define maxn 2000010
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
ll n,sum,val,s,L,R,tot;
ll l[maxn],r[maxn],v[maxn];
bool tag[maxn];
bool cmp(const ll &a,const ll &b)
{
return a>b;
}
int main()
{
read(n),r[0]=1,l[n+1]=n;
for(int i=1;i<=n;++i)
read(v[i]),sum+=v[i],l[i]=i-1,r[i]=i+1,tag[i]=(v[i]!=0);
for(int i=3;i<=n;i=r[i])
while(tag[l[l[i]]]&&tag[l[i]]&&tag[i]&&v[l[i]]>=v[l[l[i]]]&&v[l[i]]>=v[i])
v[i]=v[l[l[i]]]+v[i]-v[l[i]],r[l[l[l[i]]]]=i,l[i]=l[l[l[i]]];
L=r[0],R=l[n+1];
while(v[L]>=v[r[L]]&&tag[L]&&tag[r[L]]) s+=v[r[L]]-v[L],L=r[r[L]];
while(v[R]>=v[l[R]]&&tag[R]&&tag[l[R]]) s+=v[l[R]]-v[R],R=l[l[R]];
for(int i=L;i<=R;i=r[i])
if(tag[i])
v[++tot]=v[i];
sort(v+1,v+tot+1,cmp),v[++tot]=s;
for(int i=1;i<=tot;++i)
{
if(i&1) val+=v[i];
else val-=v[i];
}
printf("%lld %lld",(sum+val)/2,(sum-val)/2);
return 0;
}