#P3493. PA2010 Termites

    ID: 2705 传统题 1000ms 128MiB 尝试: 48 已通过: 23 难度: 10 上传者: 标签>CF2900省选/NOI-零和博弈交换论证排序贪心链表队列奇偶性分析增量维护

PA2010 Termites

[PA2010] Termites

题目描述

有一个长度为 nn 的数列 aa,两名玩家轮流行动,每次可以选择一个与 00 相邻的数字,得到数字大小的得分,并将它变为 00。求如果两个人都采取最优策略,两个人的得分。

输入格式

第一行一个整数 nn,意义如题面。

接下来一行 nn 个整数,表示这个数列。

输出格式

一行两个整数,表示两个人都采取最优策略的答案。

样例 #1

样例输入 #1

8
1 2 0 3 7 4 0 9

样例输出 #1

17 9

提示

数据规模与约定

对于全部的测试点,保证 1≤n≤1061\leq n\leq 10^6,且对于任何一个 aa 中的元素 xx,都保证 0≤x≤1060\leq x\leq 10^6 且至少存在一个 00。