$n$개의 정수로 이루어진 수열 $a_1, a_2, ... , a_n$이 주어진다. 이 수열에서 연속한 임의의 구간 $[l, r]$을 골라 $S = $$\sum\limits_{i = l}^r a_i$의 값을 구할 수 있다.

$S$를 가능한 한 크게 하는 구간 $[l, r]$을 잡았다고 할 때, $S$의 값을 구해보자. 단, $[l, r]$의 길이는 최소 $1$ 이상이라고 가정한다.

첫째 줄에 수열의 길이를 뜻하는 정수 $n$이 주어진다.$(1 ≤ n ≤ 150,000)$

둘째 줄에 $a_1, a_2, ... , a_n$이 공백으로 구분되어 주어진다. $(-10,000  ≤ a_i ≤ 10,000)$