题目描述

奶牛开了家新公司，已经连续运作了N天。她们在第i天获得了Pi元的利润，不过有些天的利润可能是负的，表示亏损。约翰想给新公司写个大新闻，以吹嘘她们的业绩。请你帮助他选出一段连续的日子，使得新公司在这段日子里的利润之和是最大的。这段日子的长度不限，但至少要包括一天。

输入格式

第一行：单个整数：N，1≤N≤10^5 第二行到N+1行：第i+1行有一个整数：Pi， −1000≤Pi≤1000

输出格式

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

样例

input

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

output

14

提示

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