题目描述

给你一个长度为 $n$ 的整数数组 $a$，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组 是数组中的一个连续部分。比如我们有一个数组$\{-2,1,-3,4,-1,2,1,-5,4\}$ ，$\{-2,1,-3\}$ 为一个连续子数组。$\{1,4,2,1\}$ 不是一个连续子数组。

输入

一共两行。

第一行为一个正整数 $n(1 \leq n \leq 10^5)$ 。

第二行包括 $n$ 个整数，两个整数之间用一个空格隔开。第 $i$ 个整数表示数组 $a$ 的元素 $a_i(-10^4 \leq a_i \leq 10^4)$ 。

输出

一行包括一个整数，表示答案。

样例

9
-2 1 -3 4 -1 2 1 -5 4

6

5
5 4 -1 7 8

23

限制

1s, 512MB 每组测试数据