问题

平面上有 $N+1$ 个点，它们分别被标记为从 $0$ 到 $N$。
虽然我们不知道每个点的位置，但对于介于 $0$ 和 $N$ 之间的整数 $i$，我们知道第 $i$ 个点和第 $i+1$ 个点之间的距离 $d_i$。
请找出 $0$ 点和 $N$ 点之间距离的最大值和最小值。

---

输入

输入以以下格式从标准输入中给出：$N$ $d_{0}$ $d_{1}$ : $d_{N-1}$

• 输入共有 $N+1$ 行。
• 第一行包含一个整数 $N(1≦N≦500)$，表示点的最大编号。
• 第二行到第 $N+1$ 行，第 $i+2$ 行 $(0 ≦ i < N)$ 包含一个整数 $d_i(1≦d_i≦30,000)$，表示第 $i$ 个点和第 $i+1$ 个点之间的距离。

输出

输出到标准输出，共有两行。
第一行是可能的最大距离，作为 $0$ 点和 $N$ 点之间的距离。
第二行是可能的最小距离，作为 $0$ 点和 $N$ 点之间的距离。
如果绝对误差或相对误差至少有一个小于等于 $10^{-3}$，则允许误差。
注意，最后要输出换行符。

---

示例 1

1
1024

输出样例 1

1024
1024

• 由输入可知，存在 $0$ 点和 $1$ 点，它们之间的距离为 $1024$。
• 所求的距离是 $0$ 点和 $1$ 点之间的距离，因此最大值和最小值都是 $1024$。

---

示例 2

3
3
4
5

输出样例 2

12
0

• 当 $0$ 点和 $3$ 点分别位于一条直线的两端时，它们之间的距离最大，如下图(a)所示，此时距离为 $3+4+5=12$。
• 当 $0$ 点和 $3$ 点重合时，它们之间的距离最小，如下图(b)所示，此时距离为 $0$。

---

示例 3

2
512
512

输出样例 3

1024
0

• 当 $0$ 点和 $2$ 点分别位于一条直线的两端时，它们之间的距离最大，如下图(a)所示，此时距离为 $512+512=1024$。
• 当 $0$ 点和 $2$ 点重合时，它们之间的距离最小，如下图(b)所示，此时距离为 $0$。

---

示例 4

3
4
8
1

输出样例 4

13
3

• 当 $0$ 点和 $3$ 点分别位于一条直线的两端时，它们之间的距离最大，如下图(a)所示，此时距离为 $4+8+1=13$。
• 由于 $0$ 点和 $3$ 点不能重合，所以当 $0$ 点和 $3$ 点位于连接点 $1$ 和点 $2$ 的线段上时，它们之间的距离最小，如下图(b)所示，此时距离为 $8-4-1=3$。

---

示例 5

10
1
2
3
4
5
6
7
8
9
10

输出样例 5

55
0

• 当 $0$ 点到 $10$ 点依次排列成直线时，它们之间的距离最大，这种情况下距离为 $1+2+3+4+5+6+7+8+9+10=55$。
• 当 $0$ 点到 $10$ 点依次排列成圆形且 $0$ 点和 $10$ 点重合时，它们之间的距离最小。

---

来源名称

ARC 004