Description

小轩购买了一支股票，并记录了这支股票最近n天内的盈亏情况P_i（盈利和亏损）。为了预测这支股票接下来的变化，他需要对这n天的盈亏情况进行总结。首先他想要从这n天内找出一段连续时间（最少一天）内的总盈利的最大值。请帮助小轩找到最大的收益和。 例如：n=7，这7天的盈亏情况分别为5、3、-1、7、8、10、-5；其中第2天到第6天的总盈利最大为11.

Format

Input

第一行包含一个整数n，表示天数； 第二行包含n个整数P₁,P₂,P₃...,P_n,分别表示每天的盈亏情况，整数之间以一个空格隔开。

Output

一个整数，表示按照题目要求得到的最大总盈利。

Samples

7
-5 3 -1 7 -8 10 -5

11

Limitation

数据范围： 测试点1～10:1<=n<=10⁵,-10⁴<=P_i<=10⁴。