Với một dãy số cho trước, bạn hãy tìm giá trị lớn nhất và nhỏ nhất của trị tuyệt đối tổng các số liên tiếp trong dãy. Cụ thể với dãy số dãy số có $n$ phần tử $a_1,a_2,...,a_n$ bạn hãy xác định giá trị của ${\displaystyle \underset{\begin{array}{c}1\le l\le r\le n\end{array}}{max}|a_l+a_{l+1}+...+a_r|}$ và ${\displaystyle \underset{\begin{array}{c}1\le l\le r\le n\end{array}}{min}|a_l+a_{l+1}+...+a_r|}$.

Đầu vào

Dòng đầu chứa số tự nhiên $n$ $(1\le n\le {10}^6)$, số phần tử của dãy.

Dòng tiếp theo gồm $n$ số nguyên là các phần tử của dãy có giá trị tuyệt đối không vượt quá ${10}^9$.

Đầu ra

Hai số tự nhiên (số lớn hơn in trước) là kết quả của bài toán.

Subtask

$30\mathrm{\%}$ số test có $n\le 100$.

$30\mathrm{\%}$ số test có $100<n\le 1000$.

Ví dụ

Đầu vào:

6
1 -2 4 2 5 2

Đầu ra:

13 1

Giải thích: GTLN là $|a_3+a_4+a_5+a_6|=4+2+5+2=13$, GTNN là $|a_1|=1$.