题目描述

奶牛们新开了一家商店，农场主约翰想知道它们的生意做得怎么样。商店已经经营了 $N$ 天（$1 \leq N \leq 100,000$），每天奶牛们都会记录当天的净利润 $P_i$（$-1,000 \leq P_i \leq 1,000$）。

约翰想找出奶牛们在任意连续时间段内获得的最大总利润。（注意：连续时间段的长度可以从一天到 $N$ 天不等。）请你编写一个程序，帮助他计算任意连续时间段内利润的最大总和。

请你写一个计算最大利润的程序来帮助他。

输入格式

• 第一行：一个整数 $N$
• 第二行到第 $N+1$ 行：第 $i+1$ 行包含一个整数 $P_i$

输出格式

• 第一行：一个整数，表示任意连续时间段内利润的最大总和。

输入输出样例 #1

输入 #1

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

输出 #1

14

说明/提示

最大总和是通过将第二到第六个数字相加得到的（$4, 9, -2, -5, 8$）=> $14$。