题目描述

张琪曼喜欢思考人生的意义,她发现每个人的一生不可能一帆风顺,或多或少总要经过 坎坷控折的考验。于是她将人的一生的每个关键时间点以数值表示，快乐值越高，分值越 商.痛苦值越高.分值越低甚至会成为负数。进一步研究,她又发现人的记忆总是会记住那 些快乐的时光，而淡忘痛苦的时光。于是她想统计出某个人连续最大的一段快乐时光总和是 多少。即给定$\red{K}$个整数的序列$\red{(N_1,N_2, ... ,N_k)}$其任意连续子序列可表示为$\red{(N_i,N_i+1,...,N_j}$ $\red{),}$其中$\red{1≤}$$\red{i≤}$$\red{j≤}$$\red{K,}$最大连续子序列是所有连续子序列中元素和最大的一个，例如，给 定序列$\red{(-2,11,-4,13,-5,-2),}$其最大连续子序列为$\red{\{11,-4,13\},}$最大和为$\red{20}$。这即 是所谓的"最大连续子序列和"问题。

输入格式

输人$\red{n(n≤}$$\red{100 000)}$和$\red{n}$个整数。

输出格式

输出该序列中最大的连续子序列的和$\red{max}$。

样例

输入样例

5
1 2 -5 11 3

输出样例

14