题目描述

奶牛们开了家新公司，这家公司已经运作了N天，财务报表显示第i天获得的利润为$P_i$，有些天的利润可能是个负数。约翰想给奶牛公司写个新闻报道，以吹嘘她们的业绩。于是他想知道，这家公司在哪一段连续的日子里，利润总和是最大的。

输入格式

第一行：单个整数N

第二行到N + 1行：每行一个整数$P_i$，代表第i天的利润，

输出格式

一行：单个整数，表示在某段连续的日子里最大的利润之和

样例

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

14

样例解释

第三天到第六天，一共是4 + 9 − 2 − 5 + 8 = 14

数据规模

• $1 ≤ N ≤ 10^5$
• $−1000 ≤ P_i ≤ 1000$