题目描述

小明正在记录自己连续 $N$ 天的收支情况，第 $i$ 天的净收入为 $P_i$ 元（可能为负数表示亏损）。

小明想找出某一段连续的日期区间，使得这段时间内的净收入总和最大。请你帮他计算这个最大值。

注意：区间长度可以从 $1$ 到 $N$（即至少包含一天）。

输入格式

第一行，一个整数 $N$。

接下来 $N$ 行，第 $i+1$ 行包含一个整数 $P_i$。

输出格式

一行，一个整数，表示所有连续时间段中利润最大和的数值。

样例

7 
-3 
4 
9 
-2 
-5 
8 
-3

14

提示

【样例解释】

取区间 $[2,6]$ 的和可以得到最大值 $14$。

数据范围：$1 \le N \le 10^5$，$|P_i| \le 1000$。