题目描述

有 $n$ 张牌，两人轮流取，且只能取两边的牌，最终每个人拿到的牌的数字和就是得分。为了得分最大，这两人每次都取两边较大的那张牌。

现给定 $n$ 与初始牌的顺序，求两人最终的分数。

输入格式

第一行一个整数 $n$，$1\le n\le 1000$。

第二行 $n$ 个整数 $a_i$，依次表示每张牌上的数字，$1\le a_i\le 1000$，保证每张牌上的数字均不相同。

输出格式

输出两个整数，依次表示每个人的得分，用一个空格分隔。

4
4 1 2 10

12 5

7
1 2 3 4 5 6 7

16 12