问题 ：纸牌游戏 (难度：中等) 竞技编程-提高思维

题目描述

侯赛因和雅罗斯拉夫正在玩纸牌游戏。桌子上排成一行有 n 张牌，每张牌上都写着不同的数字。玩家轮流。侯赛因开始游戏。在每个回合中，玩家可以拿最左边或最右边的牌。玩家将始终选择数字最大的牌。当桌子上没有牌时，游戏结束。找出 Huseyn 和 Yaroslav 在游戏结束时收集的牌上的数字之和。

输入格式

第一行包含牌的数量 n（1 ≤ n ≤ 10000），即桌面上有 n 张牌。 第二行包含 n 个正整数，每个整数表示卡片上的数字。所有数字均不大于 10^9。

输出格式

输出两行。 第一行输出侯赛因收集的牌上数字的总和。 第二行输出雅罗斯拉夫收集的牌上数字的总和。

示例

输入

7

4 7 5 1 12 8 2

输出 18 21

时间复杂度分析

• 每一轮选择最大牌，操作的时间复杂度为 O(1)，而每次操作都会减少一张牌，因此游戏的总操作次数为 n。
• 因此，整体时间复杂度为 O(n)。