【题目描述】：
    A 公司正在举办一个智力双人游戏比赛----取石子游戏，游戏的获胜者将会获得 A 公司提供的丰厚奖金，因此吸引了来自全国各地的许多聪明的选手前来参加比赛。 
    与经典的取石子游戏相比，A公司举办的这次比赛的取石子游戏规则复杂了很多： 
  总共有N堆石子依次排成一行，第i堆石子有 ai个石子。 
  开始若干堆石子已被 A公司故意拿走。 
  然后两个玩家轮流来取石子，每次每个玩家可以取走一堆中的所有石子，但有一个限制条件：一个玩家若要取走一堆石子，则与这堆石子相邻的某堆石子已被取走(之前被某个玩家取走或开始被A公司故意拿走)。注意：第 1堆石子只与第 2堆石子相邻，第N堆石子只与第N-1堆石子相邻，其余的第 i堆石子与第i-1堆和第 i+1 堆石子相邻。  
  所有石子都被取走时，游戏结束。谁最后取得的总石子数最多，谁就获得了这场游戏的胜利。 
    作为这次比赛的参赛者之一，绝顶聪明的你，想知道对于任何一场比赛，如果先手者和后手者都使用最优的策略，最后先手者和后手者分别能够取得的总石子数分别是多少。
【题目解法】：
    博弈论好题，可惜我还是太SB了TAT
    我们可以将题目抽象化，将序列由0作为分界点划分为一段段全都不为0的序列
    考虑两边的序列，如果都是紧贴着边界，那么他们只能从一段依次去取，因此看成是栈
    考虑中间的序列，他们可以从两段去取，因此看成双端队列
    现在变成：给你两个栈和若干个双端队列，如何取最优呢？
    先考虑栈：如果从栈顶到栈底是递减的，显然从栈顶开始依次取是对两边来说都是最优的
    考虑双端队列：如果不存在这样一段：... A B C ...使得 B>=A B>=C，显然从两边依次取最大值是最优的
    因此我们考虑如何将不是上面两种的情况化简
    考虑序列最边界的两个元素A B ... 或者 ... B A
    如果A>=B，显然A B最后选，因为谁都不想选B，不然就被爆了TAT
    但是总数是确定的，因此A B给谁都是确定的，删去A B
    考虑对于序列中... A B C ... B>=A B>=C的情况
    如果某个人被迫选A，那么后面那个人显然把B抢了，因为此时不存在比B更好的方案，否则先手又何必被迫选A呢？
    后手选了B，那么先手肯定选C啦，如果有比C更好的，一开始肯定就不会傻逼的取选A啦QwQ
    所以我们将A B C删去，换成A+C-B即可
    然后就变成了上面的两种情况，把所有的数弄出来，排个序，先后手交替取即可
    复杂度O(N log N)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=1000005;
struct node {int l,r; long long x; bool del;} list[N];
int n,m,tot,head,tail; long long a[N],ans1,ans2,sum; bool opt;
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
void init()
{
    n=getint(); ans1=ans2=0; m=0;
    for (int i=1; i<=n; i++)
    {
        list[i].x=getint(); sum+=list[i].x;
        list[i].del=(list[i].x==0);
        list[i].l=i-1; list[i].r=i+1;
        if (list[i].x!=0) m++;
    }
}
void del(int x)
{
    opt=true; if (list[x].del) return;
    if (list[x].l>=1) list[list[x].l].r=list[x].r;
    if (list[x].r<=n) list[list[x].r].l=list[x].l;
    if (head==x) head=list[x].r;
    if (tail==x) tail=list[x].l;
    list[x].del=true;
}
void modify_head()
{
    if (m%2==0) ans2+=list[head].x,ans1+=list[list[head].r].x;
    if (m%2==1) ans1+=list[head].x,ans2+=list[list[head].r].x;
    del(head); del(head);
}
void modify_tail()
{
    if (m%2==0) ans2+=list[tail].x,ans1+=list[list[tail].l].x;
    if (m%2==1) ans1+=list[tail].x,ans2+=list[list[tail].l].x;
    del(tail); del(tail);
}
void clarify()
{
    head=1,tail=n;
    for (opt=true;(opt)&&(head<tail);)
    {
        opt=false;
        while ((!list[head].del)&&(!list[list[head].r].del)&&(list[head].x>=list[list[head].r].x)) modify_head();
        while ((!list[tail].del)&&(!list[list[tail].l].del)&&(list[tail].x>=list[list[tail].l].x)) modify_tail();
        for (int i=head; i<=tail; i++)
        {
            if ((list[i].l<1)||(list[i].r>n)||(list[i].del)) continue;
            if ((list[list[i].l].del)||(list[list[i].r].del)) continue;
            if ((list[list[i].l].x>list[i].x)||(list[list[i].r].x>list[i].x)) continue;
            list[i].x=list[list[i].l].x+list[list[i].r].x-list[i].x;
            del(list[i].l); del(list[i].r);
        }
    }
}
void solve()
{
    for (int i=1; i<=n; i++) if (!list[i].del) a[++tot]=list[i].x;
    sort(a+1,a+tot+1); sum-=(ans1+ans2); long long now=0;
    for (int i=tot; i>=1; i--) if (tot%2==i%2) now+=a[i]; else now-=a[i];
    ans1+=(sum+now)/2; ans2+=(sum-now)/2;
    printf("%lld %lld\n",ans1,ans2);
}
int main()
{
    init();
    clarify();
    solve();
    return 0;
}