#3. L·篮球队招新

时间限制：1000MS
内存限制：131072KB

额外编译参数: C/C++:-O2 Pascal:-O2

题目描述

一年一度的篮球队招新又开始了，队长 CJG 精挑细选，选出 n 个优秀的球员。

为了测试这些球员的能力，CJG 让球员们站成一排，每次会选出相邻的两名球员出来比赛，赢的回到原来的位置，输的下场休息。

出乎 CJG 意料的是，这些球员的技术出奇的均衡，唯一决定胜负的就是球员的体力了。一开始每个球员都有一定的体力，每次比赛，总是体力更多的球员获胜，并且比赛中他要消耗与对方体力等值的体力。

而且比赛都进行地很快，在一旁观战时所恢复的体力可以忽略不计。

CJG 打算在经过反复地战斗后，与留下的最后一个人进行决斗，所以他想要知道最后留下的一个人的最大体力和最小体力。

（如果最后一局可以恰好打平，那么最小体力就是 0。）

输入格式

第一行输入一个整数 n。

第二行输入 n 个整数，分别表示每个队员的初始体力。

输出格式 输出一行，包括两个整数，分别是最大体力和最小体力。

样例 1 输入

4

3 7 6 8

样例 1 输出

6 2

样例 2 输入

5

3 1 7 2 9

样例 2 输出

8 0

数据规模与约定

对于 30% 的数据，输入的数均不超过 30。

对于 70% 的数据，输入的数均不超过 60。

对于 100% 的数据，输入的数均不超过 110。