题目描述

在算法竞赛的历史上，区间问题一直是竞赛选手们又爱又恨的一个经典问题，很多耳熟能详的算法都是解决区间问题的，例如，线段树、树状数组、莫队…… 所以，小L也想出一道和区间相关的难题来难一难正在打比赛的你。 小L给你一个长度为 $n$ 的序列 $a$，对这个序列我们定义一种美丽值。对于区间 [$l$ , $r$] ($l \\leq r$)美丽值的含义是 $∑_{i=l}^{r}{a_i}$ 。 请你求出这个序列中最大的美丽值。一段区间存在美丽值需要这个区间 [$l$ , $r$]满足 $1 \\leq l \\leq r \\leq n$ 的关系。

输入格式

第一行一个数，表示 $n$ 。 第二行 $n$ 个数，表示序列 $a$ 。

$1 \\leq n \\leq 10^5$ $-10^9 \\leq a_i \\leq 10^9$

输出格式

一个数字，表示答案。

样例

5 
5 4 -6 3 5

11

5 
-2 -4 -6 -8 -10

-2

提示

by 励翔 2022春第二次排位赛