Background

输入一个 非空 整型数组，数组里的数可能为正，也可能为负。

求所有子段的和的最大值。

Input

第一行一个整数 $n$,

第二行 $n$ 个整数 $a_i$

Output

一个整数，代表最大子段和

Samples

8
1 -2 3 10 -4 7 2 -5

18

Limitation

$n<=100000$

$-10000<=a_i<=10000$