题目描述

srf 很强。他特别喜欢在 scz 的机房切题，一边切题，一边发出让蒟蒻们颤抖的声音。

“这道黑题不就是个暴力吗，随便写写就过了。”“欸，我怎么 A 题了。”

一天，srf 切到了按顺序排列的 $n$ 道简单题，每道题都有一个毒瘤程度 $a_i$。由于 srf 的特殊性，他每次可以选择连续的两道题切掉。 当他切掉了这两道题时，他就会吸收这两道题的精华，想出一道新的题放在原处，新题的毒瘤程度为原先两道题的毒瘤程度之和。这道新题的毒瘤程度即为这次切题的得分。

srf 想知道他得分的最大值。

但是 qty 看到 srf 切题很不爽，诅咒他得到分数的最小值。

qty 想知道这个最小值。

srf 和 qty 觉得这个题太水了，就把问题丢给了在一旁看热闹的 pcf。

pcf 也不想做，问题就交给了你。

输入格式

第一行一个正整数 $n$（$1\le n\le 500$），表示题目数量。 第二行，$n$ 个正整数 $a_1$，$a_2$，$a_3\cdots a_n$，表示每道题的毒瘤程度。

输出格式

一行两个正整数，表示最大的得分和和最小的得分和。

4
6 14 1 4

66 49

数据范围

$1\le n\le 500$

$1\le a_i \le 10^4$