候车厅

时间限制：$1.0\text{ s}$

空间限制：$64\text{ MiB}$

题目描述

城市接驳站在每天运营前，会有一部分乘客已经在候车厅内等待。工作人员本应记录这时的人数，但今天的第一条记录丢失了。

幸运的是，之后的闸机日志仍然完整。日志共有 $n$ 条，第 $i$ 条记录一个整数 $d_i$：

• 若 $d_i>0$，表示有 $d_i$ 名乘客进入候车厅；
• 若 $d_i<0$，表示有 $-d_i$ 名乘客离开候车厅；
• 若 $d_i=0$，表示完成了一次核验，但厅内人数没有变化。

每条日志执行后，候车厅内的人数都不可能为负数。现在需要补回丢失的初始人数。为了不凭空增加乘客，工作人员希望这个初始人数尽量小。

在采用最小初始人数后，还要确定候车厅在这段记录中至少需要容纳多少人。这里把第一条日志之前的初始时刻，以及每条日志执行后的时刻都计入统计；这些时刻中的最大人数就是所需容量。

请你求出最小初始人数和对应的所需容量。

输入格式

第一行一个正整数 $n$，表示日志条数。

第二行 $n$ 个整数 $d_1,d_2,\ldots,d_n$，依次表示每条日志带来的人数变化。

输出格式

输出一行两个整数，依次表示最小初始人数和采用该初始人数时的所需容量。

输入样例 1

6
4 -7 3 2 -5 6

输出样例 1

3 7

样例 1 解释

若初始有 $3$ 人，各时刻人数依次为

人数始终非负，峰值为 $7$。若初始人数小于 $3$，执行第二条日志后人数就会变成负数。

输入样例 2

5
-2 -3 10 -4 -1

输出样例 2

5 10

输入样例 3

见附件 sample/lobby3.in

输出样例 3

见附件 sample/lobby3.out

数据范围

对于所有测试点，保证 $1\le n\le 10^6$，$-10^9\le d_i\le 10^9$。

每个测试点单独计分。