题目描述

将 \(N\) 个整数排成一行，每个整数 \(a[i]\) 的值在\(-10000 ≤ a[i] ≤10000\)之内。然后从这一行数中进行取数，其规则是：可从这一行中的任何一个位置开始取数，到任何位置结束，但不能不取。找出一种取法，使得取得的和为最大，再找出一种取法，使得取得的和为最小。例如： \(N=4，4\) 个数依次为：\(13，-6，7，-8\)。取得和为最大的是：\(14\)，取得和为最小的是：\(-8\)。

格式

输入格式

第一行有一个整数 \(N\)，第二行为 \(N\) 个整数。

输出格式

输出二行，第一行一个整数表示取得和的最大值，第二行一个整数表示取得和的最小值。

样例1

样例输入1

4
13 -6 7 -8

样例输出1

14
-8

限制

\(50\%\) 的数据：\(1 ≤N ≤100\)；
\(100\%\) 的数据：\(1 ≤N ≤100000\)。