Description

考虑一个由两个玩家玩的游戏。游戏开始前给定一串排成一排的N个数字。两位玩家轮流从这一串数中的最左端或者最右端取出一个数。当所有数字都被取完后，游戏结束。此时，两位玩家各自的得分将是他所有取出的数的和。得分较高的玩家获胜。
假设你是先取者。请编写程序制定一个游戏的最佳策略。最佳策略是指这样一种数字取法，它能在最坏的情况（后取者的策略对自己最不利的情况）下得到最高的得分。

Format

Input

从文件game2.in中读入数据。
数据的第一行是一个正整数N，输入数据保证1<=N<=100。
第二行从左至右给出了游戏初始时的N个正整数。这些正整数保证不超过200。

Output

在game2.out中输出两个用空格隔开的正整数。他们分别表示游戏的先取者在最坏情况下最高的得分和此时后取者的得分。

Sample 1

Input

6
4 7 2 9 5 2

Output

18 11

Limitation

1s, 10MiB for each test case.